
#include <algorithm>
#include <iostream>
#include <cstdio>
#include <ctime>

#include "SpaEnumTranslator.h"
#include "QueryEvaluator.h"
#include "Optimizer.h"

const std::string QueryEvaluator::TRUE_RESULT = "true";
const std::string QueryEvaluator::FALSE_RESULT = "false";

const int QueryEvaluator::ERROR_COPYTABLEROWS_ROWTODUPLICATE_DOES_NOT_EXIST = -1;
const int QueryEvaluator::ERROR_COPYTABLEROWS_ROWTOCOPYFROM_DOES_NOT_EXIST = -2;

QueryEvaluator::QueryEvaluator(PKB *pkb) {
	mPkb = pkb;
}

QueryEvaluator::~QueryEvaluator(void) {
}

std::vector<string>& QueryEvaluator::evaluateQuery(const QueryTable& queryTable) {

	//cout << "\n\nQueryEvaluator evaluateQuery()\n";

	mResultTable = queryTable.mResultTable;
	mResultGraphTable = ResultGraphTable();
	mSynonymResultsTables = SynonymResultsTablePtrMap();
	mSynonymTable = queryTable.mSynonymTable;
	mConstraintTable = queryTable.mConstraintTable;
	mRelationshipClauseTable = queryTable.mRelClauseTable;
	mPatternTable = queryTable.mPatternTable;

	std::vector<string> *results = NULL;

	results = &evaluateQueryUsingResultGraphTableUsingOptimizer();
	//results = &evaluateQueryUsingTableUsingOptimizer();
	//results = &evaluateQueryUsingResultGraphTable();
	//results = &evaluateQueryUsingTable();
	
	return *results;
}

std::vector<std::string>& QueryEvaluator::evaluateQueryUsingResultGraphTableUsingOptimizer() {
	Optimizer::ClauseSet clauseSet;
	// Convert all entries into clauses and then into the clauseSet
	for (int i = 0; i < mRelationshipClauseTable.getNumberOfEntries(); i++) {
		RelationshipEntry *relEntry = new RelationshipEntry(mRelationshipClauseTable.getRelationshipEntry(i));
		clauseSet.push_back(Clause::createClause(relEntry));
	}
	for (int i = 0; i < mPatternTable.getNumberOfEntries(); i++) {
		PatternEntry *patEntry = new PatternEntry(mPatternTable.getPatternEntryAtIndex(i));
		clauseSet.push_back(Clause::createClause(patEntry));
	}
	for (int i = 0; i < mConstraintTable.getNumberOfEntries(); i++) {
		ConstraintEntry *conEntry = new ConstraintEntry(mConstraintTable.getConstraintEntry(i));
		clauseSet.push_back(Clause::createClause(conEntry));
	}
	
	// Create an optimizer, giving it the clause set
	Optimizer *optimizer = new Optimizer(clauseSet, &mSynonymTable, mPkb);
	bool isQueryValid = evaluateUsingResultGraphTableWithOptimizer(optimizer);

	std::vector<string> *results = NULL;
	//cout << "Getting results, queryValid = " << isQueryValid << endl;
	if (isQueryValid) {
		results = &getResultsForProjectionUsingResultGraphTable(true);
	} else {
		results = &getResultsForProjectionUsingResultGraphTable(false);
	}
	return *results;
}

bool QueryEvaluator::evaluateUsingResultGraphTableWithOptimizer(Optimizer *optimizer) {
	bool isQueryValid = true;
	int count = 1;
	while (isQueryValid && optimizer->isAnyClauseLeft()) {
		// Keep picking the least complex clause, evaluate it and then remove it from optimizer, then update optimizer
		optimizer->updateComplexityValues(mResultGraphTable);
		const Clause &clause = optimizer->getLeastComplexityClause();
		//cout << "Evaluating #" << count++ << " clause = " << Utilities::clauseToString(clause) << endl;
		isQueryValid = evaluateOneClauseUsingResultGraphTable(clause);
		optimizer->removeLeastComplexityClause();
	}
	return isQueryValid;
}

bool QueryEvaluator::evaluateOneClauseUsingResultGraphTable(const Clause &clause) {
	bool isClauseValid = true;
	switch (clause.type) {
	case Clause::TYPE_RELATIONSHIP_CLAUSE:
		isClauseValid = evaluateOneRelationshipClauseUsingResultGraphTable(*clause.relationshipEntry);
		break;
	case Clause::TYPE_PATTERN_CLAUSE:
		isClauseValid = evaluateOnePatternUsingResultGraphTable(*clause.patternEntry);
		break;
	default: // WITH_CLAUSE
		isClauseValid = evaluateOneWithClauseUsingResultGraphTable(*clause.constraintEntry);
		break;
	}
	return isClauseValid;
}

// Uses the table algorithm and Optimizer to evaluate the entire query
std::vector<std::string>& QueryEvaluator::evaluateQueryUsingTableUsingOptimizer() {
	Optimizer::ClauseSet clauseSet;
	// Convert all entries into clauses and then into the clauseSet
	for (int i = 0; i < mRelationshipClauseTable.getNumberOfEntries(); i++) {
		RelationshipEntry *relEntry = new RelationshipEntry(mRelationshipClauseTable.getRelationshipEntry(i));
		clauseSet.push_back(Clause::createClause(relEntry));
	}
	for (int i = 0; i < mPatternTable.getNumberOfEntries(); i++) {
		PatternEntry *patEntry = new PatternEntry(mPatternTable.getPatternEntryAtIndex(i));
		clauseSet.push_back(Clause::createClause(patEntry));
	}
	for (int i = 0; i < mConstraintTable.getNumberOfEntries(); i++) {
		ConstraintEntry *conEntry = new ConstraintEntry(mConstraintTable.getConstraintEntry(i));
		clauseSet.push_back(Clause::createClause(conEntry));
	}
	
	// Create an optimizer, giving it the clause set
	Optimizer *optimizer = new Optimizer(clauseSet, &mSynonymTable, mPkb);
	bool isQueryValid = evaluateUsingTableWithOptimizer(optimizer);

	std::vector<string> *results = NULL;
	if (isQueryValid) {
		results = &getResultsForProjectionUsingTable(true);
	} else {
		results = &getResultsForProjectionUsingTable(false);
	}
	return *results;
}

// Evaluates all the clauses in the Optimizer with the table algorithm
bool QueryEvaluator::evaluateUsingTableWithOptimizer(Optimizer *optimizer) {
	bool isQueryValid = true;
	int count = 1;
	while (isQueryValid && optimizer->isAnyClauseLeft()) {
		// Keep picking the least complex clause, evaluate it and then remove it from optimizer, then update optimizer
		optimizer->updateComplexityValues(mSynonymResultsTables);
		const Clause &clause = optimizer->getLeastComplexityClause();
		//cout << "Evaluating #" << count++ << " clause = " << Utilities::clauseToString(clause) << endl;
		isQueryValid = evaluateOneClauseUsingTable(clause);
		optimizer->removeLeastComplexityClause();
	}
	return isQueryValid;
}

// Uses the table algorithm to evaluate one clause
bool QueryEvaluator::evaluateOneClauseUsingTable(const Clause &clause) {
	bool isClauseValid = true;
	switch (clause.type) {
	case Clause::TYPE_RELATIONSHIP_CLAUSE:
		isClauseValid = evaluateOneRelationshipClauseUsingTable(*clause.relationshipEntry);
		break;
	case Clause::TYPE_PATTERN_CLAUSE:
		isClauseValid = evaluateOnePatternUsingTable(*clause.patternEntry);
		break;
	default: // WITH_CLAUSE
		isClauseValid = evaluateOneWithClauseUsingTable(*clause.constraintEntry);
		break;
	}
	return isClauseValid;
}

// Uses the graph algorithm to evaluate the entire query
std::vector<std::string>& QueryEvaluator::evaluateQueryUsingResultGraphTable() {
	std::vector<std::string> *results = NULL;

	bool isConstraintTrue = evaluateAllWithClausesUsingResultGraphTable();
	if ( !isConstraintTrue) {
		// Immediately return false/empty result
		results = &getResultsForProjectionUsingResultGraphTable(false);
		return *results;
	}

	bool isRelationshipTrue = evaluateAllRelationshipClausesUsingResultGraphTable();
	if ( !isRelationshipTrue) {
		// Immediately return false/empty result
		results = &getResultsForProjectionUsingResultGraphTable(false);
		return *results;
	}

	bool isPatternTrue = evaluateAllPatternsUsingResultGraphTable();	
	if (isConstraintTrue && isRelationshipTrue && isPatternTrue) {
		results = &getResultsForProjectionUsingResultGraphTable(true);
	} else {
		results = &getResultsForProjectionUsingResultGraphTable(false);
	}

	return *results;
}

// Uses the table algorithm to evaluate the entire query
std::vector<std::string>& QueryEvaluator::evaluateQueryUsingTable() {
	std::vector<std::string> *results = NULL;

	bool isConstraintTrue = evaluateAllWithClausesUsingTable();
	if ( !isConstraintTrue) {
		// Immediately return false/empty result
		results = &getResultsForProjectionUsingTable(false);
		return *results;
	}

	bool isRelationshipTrue = evaluateAllRelationshipClausesUsingTable();
	if ( !isRelationshipTrue) {
		// Immediately return false/empty result
		results = &getResultsForProjectionUsingTable(false);
		return *results;
	}

	bool isPatternTrue = evaluateAllPatternsUsingTable();	
	if (isConstraintTrue && isRelationshipTrue && isPatternTrue) {
		results = &getResultsForProjectionUsingTable(true);
	} else {
		results = &getResultsForProjectionUsingTable(false);
	}

	return *results;
}

// Updates the mSynonymResultsTables with the given good indexes for synonym
bool QueryEvaluator::updateTableWithGoodIndexes(std::string synonym1, const IntBoolMap& goodIndexesMap) {
	
	if (goodIndexesMap.size() == 0) {
		// No good indexes for a synonym, so immediately return false
		return false;
	}


	std::clock_t start;
	double duration;

	start = std::clock(); // time how long updateTableWithGoodIndexes takes
		
	

	if (mSynonymResultsTables.find(synonym1) == mSynonymResultsTables.end()) {
		// Synonym1 has no table for it, so we create one for it and put the goodIndexes in.
		SynonymResultsTable *table = new SynonymResultsTable();

		table->insertColumn(synonym1);

		for (auto it = goodIndexesMap.begin(); it != goodIndexesMap.end(); it++) {
			table->appendEntry(synonym1, it->first);
		} 
		mSynonymResultsTables[synonym1] = table;

	} else {
		// Synonym1 has a table for it, so we remove all rows in which synonym1 does not have an
		// entry that is in the goodIndexesMap
		SynonymResultsTable *table = mSynonymResultsTables.at(synonym1);
		Table<std::string, int>::Column& column1 = table->getColumn(synonym1);
		for (int i = (int)column1.size() - 1; i >= 0; i--) {
			// Note that we go backwards because we delete on the go.
			// Check each entry in the row to see if the index is in the goodIndexesMap
			int item = column1.at(i);
			if ( !Utilities::isKeyInMap_TypeType(goodIndexesMap, item)) {
				// Item not in the goodIndexesMap, so we must delete it
				table->deleteRow(i);
			}
		}
	}



	duration = ( std::clock() - start ) / (double) CLOCKS_PER_SEC;
	//cout << "updateTableWithGoodIndexes() that resulted in a table of numRows = " << mSynonymResultsTables.at(synonym1)->getNumRows()
	//	<< " and numCols = " << mSynonymResultsTables.at(synonym1)->getHeaders().size() << " took " << duration << " seconds\n";



	// Here, we are ensured that we have a table for synonym1.
	// If it is empty it means that we have no possible answers.
	if (mSynonymResultsTables.at(synonym1)->getNumRows() > 0) {
		return true;
	} else {
		return false;
	}
}

// Updates the mSynonymResultsTables with the given relationship between synonym1 and synonym2,
// possibly connecting multiple tables if synonym1 and synonym2 are in separate tables
bool QueryEvaluator::updateTablesWithNewRelationship(std::string synonym1, std::string synonym2, RelationshipType relType) {
	/*---------------------------------------------------------
	 *	3 Main Cases
	 *
	 *	Case 1: Neither synonym1 nor synonym2 have tables.
	 *
	 *	Case 2: Only synonym1 OR synonym2 have a table, 
	 *			but not both.
	 *		2a: Synonym1 has the table.
	 *		2b: Synonym2 has the table.
	 *
	 *	Case 3: Both synonym1 AND synonym2 have tables.
	 *		3a: Synonym1 AND synonym2 are in the same table.
	 *		3b: Synonym1 AND synonym2 are in different tables.
	 *---------------------------------------------------------*/


	std::clock_t start;
	double duration;

	start = std::clock(); // time how long updateTableWithGoodIndexes takes



	bool doesSynonym1HaveTable = (mSynonymResultsTables.find(synonym1) != mSynonymResultsTables.end());
	bool doesSynonym2HaveTable = (mSynonymResultsTables.find(synonym2) != mSynonymResultsTables.end());

	// So that we don't evaluate the same index multiple times, we store the IntBoolMap gotten after
	// requesting it from the PKB into this unordered_map.
	std::unordered_map<int, IntBoolMap*> trueRelationshipPairsMap; 

	if ( !doesSynonym1HaveTable && !doesSynonym2HaveTable) {
		/*---------------------------------------------------------
		 *	Case 1: Neither synonym1 nor synonym2 have tables.
		 *	
		 *	Solution: Create one table containing them,
		 *		get the true relationship pairs (TRPairs),
		 *		and fill up their columns with their TRPairs.
		 *
		 *		Then include the <synonym1, table*> and 
		 *		<synonym2, table*> pairs in the mSynonymResultsTables.
		 *---------------------------------------------------------*/
		// Create table containing both synonyms
		SynonymResultsTable* table = NULL;
		if (synonym1 == synonym2) {
			// Special case when synonym1 is synonym2
			table = new SynonymResultsTable();
			table->insertColumn(synonym1);
		} else {
			// Normal case when synonym1 is NOT synonym2
			table = new SynonymResultsTable(synonym1, synonym2);
		}

		// Get TRPairs
		std::unordered_map<int, IntBoolMap*>& trueRelationshipPairs = getAllTrueRelationshipPairs(synonym1, synonym2, relType);
		// Fill up columns with TRPairs
		for (auto it1 = trueRelationshipPairs.begin(); it1 != trueRelationshipPairs.end(); it1++) {
			int index1 = it1->first;
			if (synonym1 == synonym2) {
				// Special case when synonym1 is synonym2, just insert all the index1 
				// into the synonym1 column and continue to the next one.
				table->appendEntry(synonym1, index1);
				continue;
			} else {
				IntBoolMap *indexesOfSynonym2 = it1->second;
				for (auto it2 = indexesOfSynonym2->begin(); it2 != indexesOfSynonym2->end(); it2++) {
					int index2 = it2->first;
					table->appendEntry(synonym1, index1);
					table->appendEntry(synonym2, index2);
				}
			}
		}

		// Include <synonym1, table*> and <synonym2, table*> into the mSynonymResultsTables
		mSynonymResultsTables[synonym1] = table;
		mSynonymResultsTables[synonym2] = table;

	} else if (doesSynonym1HaveTable && !doesSynonym2HaveTable) {
		/*---------------------------------------------------------
		 *	Case 2a: Synonym1 has the table, but synonym2 doesn't.
		 *	
		 *	Solution: Insert column for synonym2 into the table,
		 *		get the true relationship pairs (TRPairs),
		 *		walk through the synonym1 column while checking
		 *		the TRPairs if there are pairs for the current
		 *		synonym1 item. If there are, then find out the
		 *		number of times the row should be duplicated
		 *		(numPairs for the item - 1) and then insert
		 *		all the new items for synonym2 to these rows.
		 *
		 *		Then include the <synonym2, table*> pair
		 *		in the mSynonymResultsTables.
		 *---------------------------------------------------------*/
		SynonymResultsTable *table = mSynonymResultsTables.at(synonym1);

		// Insert the column for synonym2 into the table
		table->insertColumn(synonym2);

		// Walk through the synonym1 column
		int numRowsDeleted = 0;
		int numRowsDuplicated = 0;
		int realTableIndex = 0;
		Table<std::string, int>::Column& column1 = table->getColumn(synonym1);
		std::vector<int> trueSynonym2IndexesToAppend; // Used at the end for appending
		for (unsigned int i = 0; i < column1.size(); i++) {
			// The index i deals with the static column1, but the realTableIndex 
			// (since it is undergoing row-deletion) is actually i - numRowsDeleted
			// row-duplication happens too, but duplicated rows are appended.
			realTableIndex = i - numRowsDeleted;

			int index1 = column1.at(i);

			// Get TRPairs for this index1
			IntBoolMap *trueSynonym2Indexes = NULL;
			if (Utilities::isKeyInMap_TypeType(trueRelationshipPairsMap, index1)) {
				trueSynonym2Indexes = trueRelationshipPairsMap.at(index1);
			} else {
				trueSynonym2Indexes = &getTrueRelationshipSynonym2IndexesForGivenSynonym1Index(relType, synonym1, synonym2, index1);
				trueRelationshipPairsMap[index1] = trueSynonym2Indexes;
			}

			if (trueSynonym2Indexes->size() == 0) {
				// Delete the row because no synonym2 indexes satisfy the relationship with this index1.
				table->deleteRow(realTableIndex);
				numRowsDeleted++;
			} else {
				// Duplicate the correct number of rows, and insert these synonym2 indexes in.
				int duplicatesRequired = trueSynonym2Indexes->size() - 1;
				if (duplicatesRequired > 0) {
					table->duplicateRow(realTableIndex, duplicatesRequired); // duplicated at the end
					numRowsDuplicated += duplicatesRequired;
				}
				// Insert the first item first,
				// and the rest into a tempVector that we use later to append at the end
				auto it = trueSynonym2Indexes->begin();
				table->appendEntry(synonym2, it->first);
				it++;
				for (; it != trueSynonym2Indexes->end(); it++) {
					int index2 = it->first;
					// We store the other indexes to be appended
					trueSynonym2IndexesToAppend.push_back(index2);
				}
			}
		}
		// Now, we append all the indexes
		for (auto it = trueSynonym2IndexesToAppend.begin(); it != trueSynonym2IndexesToAppend.end(); it++) {
			table->appendEntry(synonym2, *it);
		}

		// Insert <synonym2, table*> into the mSynonymResultsTables
		mSynonymResultsTables[synonym2] = table;

	} else if ( !doesSynonym1HaveTable && doesSynonym2HaveTable) {
		/*---------------------------------------------------------
		 *	Case 2b: Synonym2 has the table, but synonym1 doesn't.
		 *	
		 *	Solution: Insert column for synonym1 into the table,
		 *		get the true relationship pairs (TRPairs),
		 *		walk through the synonym2 column while checking
		 *		the TRPairs if there are pairs for the current
		 *		synonym2 item. If there are, then find out the
		 *		number of times the row should be duplicated
		 *		(numPairs for the item - 1) and then insert
		 *		all the new items for synonym1 to these rows.
		 *
		 *		Then include the <synonym1, table*> pair
		 *		in the mSynonymResultsTables.
		 *---------------------------------------------------------*/
		SynonymResultsTable *table = mSynonymResultsTables.at(synonym2);

		// Insert the column for synonym2 into the table
		table->insertColumn(synonym1);

		// Walk through the synonym1 column
		int numRowsDeleted = 0;
		int numRowsDuplicated = 0;
		int realTableIndex = 0;
		Table<std::string, int>::Column& column2 = table->getColumn(synonym2);
		std::vector<int> trueSynonym1IndexesToAppend; // Used at the end for appending
		for (unsigned int i = 0; i < column2.size(); i++) {
			// The index i deals with the static column1, but the realTableIndex 
			// (since it is undergoing row-deletion) is actually i - numRowsDeleted
			// row-duplication happens too, but duplicated rows are appended.
			realTableIndex = i - numRowsDeleted;

			int index2 = column2.at(i);

			// Get TRPairs for this index2
			IntBoolMap *trueSynonym1Indexes = NULL;
			if (Utilities::isKeyInMap_TypeType(trueRelationshipPairsMap, index2)) {
				trueSynonym1Indexes = trueRelationshipPairsMap.at(index2);
			} else {
				trueSynonym1Indexes = &getTrueRelationshipSynonym1IndexesForGivenSynonym2Index(relType, synonym1, synonym2, index2);
				trueRelationshipPairsMap[index2] = trueSynonym1Indexes;
			}

			if (trueSynonym1Indexes->size() == 0) {
				// Delete the row because no synonym1 indexes satisfy the relationship with this index2.
				table->deleteRow(realTableIndex);
				numRowsDeleted++;
			} else {
				// Duplicate the correct number of rows, and insert these synonym1 indexes in.
				int duplicatesRequired = trueSynonym1Indexes->size() - 1;
				if (duplicatesRequired > 0) {
					table->duplicateRow(realTableIndex, duplicatesRequired);
					numRowsDuplicated += duplicatesRequired;
				}
				// Insert the first item first,
				// and the rest into a tempVector that we use later to append at the end
				auto it = trueSynonym1Indexes->begin();
				table->appendEntry(synonym1, it->first);
				it++;
				for (; it != trueSynonym1Indexes->end(); it++) {
					int index1 = it->first;
					// We store the other indexes to be appended
					trueSynonym1IndexesToAppend.push_back(index1);
				}
			}
		}
		// Now, we append all the indexes
		for (auto it = trueSynonym1IndexesToAppend.begin(); it != trueSynonym1IndexesToAppend.end(); it++) {
			table->appendEntry(synonym1, *it);
		}

		// Insert <synonym1, table*> into the mSynonymResultsTables
		mSynonymResultsTables[synonym1] = table;
	} else {
		/*---------------------------------------------------------
		 *	Case 3: Both synonym1 AND synonym2 have tables.
		 *---------------------------------------------------------*/
		SynonymResultsTable *table1 = mSynonymResultsTables.at(synonym1);
		SynonymResultsTable *table2 = mSynonymResultsTables.at(synonym2);
		if (table1 == table2) {
			/*---------------------------------------------------------
			 *	Case 3a: Both synonym1 AND synonym2 are in the same table.
			 *
			 *	Solution: Walk through the synonym1 column while checking
			 *		the TRPairs if there are pairs for the current synonym1
			 *		item. If there are, check if the TRPairs contains
			 *		the corresponding synonym2 item in the current row.
			 *		If so, we merely continue walking.
			 *		If not, we have to delete this row.
			 *---------------------------------------------------------*/

			// Walk through the synonym1 column
			int numRowsDeleted = 0;
			int realTableIndex = 0;
			Table<std::string, int>::Column& column1 = table1->getColumn(synonym1);
			Table<std::string, int>::Column& column2 = table1->getColumn(synonym2); // Use table1 also because table1 == table2
			for (unsigned int i = 0; i < column1.size(); i++) {
				// The index i deals with the static column1, but the realTableIndex 
				// (since it is undergoing row-deletion) is actually i - numRowsDeleted
				realTableIndex = i - numRowsDeleted;

				int index1 = column1.at(i);

				// Get TRPairs for this index1
				IntBoolMap *trueSynonym2Indexes = NULL;
				if (Utilities::isKeyInMap_TypeType(trueRelationshipPairsMap, index1)) {
					trueSynonym2Indexes = trueRelationshipPairsMap.at(index1);
				} else {
					trueSynonym2Indexes = &getTrueRelationshipSynonym2IndexesForGivenSynonym1Index(relType, synonym1, synonym2, index1);
					trueRelationshipPairsMap[index1] = trueSynonym2Indexes;
				}

				// Check if the corresponding index of synonym2 in the current row is contained in this TRPairs
				int index2 = column2.at(i);
				if (Utilities::isKeyInMap_TypeType(*trueSynonym2Indexes, index2)) {
					// If yes, just continue walking because this is a valid row
					continue;
				} else {
					// If no, then this is not a valid row, so delete it
					table1->deleteRow(realTableIndex);
					numRowsDeleted++;
				}
			}
		} else {
			/*---------------------------------------------------------
			 *	Case 3b: Synonym1 and synonym2 are in different tables
			 *
			 *	Solution: First, for efficiency, we look at table2 and
			 *		create a unordered_map that is keyed by the item value
			 *		and which elements are the set of row indexes
			 *		at which the item value is contained. 
			 *		Call this unordered_map M.
			 *
			 *		Then, look at table1, walk through the synonym1
			 *		column while checking if TRPairs contains the 
			 *		item.
			 *		If it does, then for each of the synonym2 indexes
			 *		in TRPairs, we look up M to find the row indexes,
			 *		and then copy these rows onto table1 one by one,
			 *		duplicating the row after each copying.
			 *		indexes into this table1. Then, delete the original row
			 *		and proceed to the last duplicated row.
			 *		(To proceed to the last duplicated row we will
			 *		 need to keep track of the number of rows copied)
			 *		If it doesn't, then just delete the row.
			 *
			 *		Override <synonym2, table1*> into the mSynonymResultsTables
			 *---------------------------------------------------------*/
			// Map M, that contains the list of row indexes in synonym2 column that contains the key value
			std::unordered_map<int, std::vector<int>> synonym2RowIndexesMap; 
			// Initialize unordered_map M by walking through synonym2 column once
			const Table<std::string, int> *table2 = mSynonymResultsTables.at(synonym2); // use const, because we do not want this to change
			Table<std::string, int>::Column& column2 = table2->getColumn(synonym2);
			for (unsigned int i = 0; i < column2.size(); i++) {
				int item = column2.at(i);
				// Ensure that the item has a list for it
				if ( !Utilities::isKeyInMap_TypeType(synonym2RowIndexesMap, item)) {
					synonym2RowIndexesMap.insert( std::pair<int, std::vector<int>>(item, std::vector<int>()) );
				}
				// Here, we are ensured the item has a list for it so insert the row index
				std::vector<int> *synonym2RowIndexes = &synonym2RowIndexesMap.at(item);
				synonym2RowIndexes->push_back(i);
			}

			// Then, walk through synonym 1 column
			int numRowsDeleted = 0;
			int numRowsDuplicated = 0;
			int realTableIndex = 0;
			Table<std::string, int> *table1 = mSynonymResultsTables.at(synonym1);
			Table<std::string, int>::Column& column1 = table1->getColumn(synonym1);
			for (unsigned int i = 0; i < column1.size(); i++) {
				realTableIndex = i + numRowsDuplicated - numRowsDeleted;
				int index1 = column1.at(i);
				
				// Get TRPairs for this index1
				IntBoolMap *trueSynonym2Indexes = NULL;
				if (Utilities::isKeyInMap_TypeType(trueRelationshipPairsMap, index1)) {
					trueSynonym2Indexes = trueRelationshipPairsMap.at(index1);
				} else {
					trueSynonym2Indexes = &getTrueRelationshipSynonym2IndexesForGivenSynonym1Index(relType, synonym1, synonym2, index1);
					trueRelationshipPairsMap[index1] = trueSynonym2Indexes;
				}

				// For each of the trueSynonym2Indexes, look up M to find the row indexes,
				// and then copy these rows onto table 1.
				bool foundTrueSynonym2 = false;
				for (auto it = trueSynonym2Indexes->begin(); it != trueSynonym2Indexes->end(); it++) {
					int trueSynonym2Index = it->first;
					// Look up M to find the row indexes
					if (Utilities::isKeyInMap_TypeType(synonym2RowIndexesMap, trueSynonym2Index)) {
						foundTrueSynonym2 = true;
						// Might need to duplicate rows
						const std::vector<int> &synonym2RowIndexes = synonym2RowIndexesMap.at(trueSynonym2Index);
						// For each of these row indexes, copy their row from table2 and onto table1
						numRowsDuplicated += copyTableRows(*table1, realTableIndex, *table2, synonym2RowIndexes);
					}
				}
				if ( !foundTrueSynonym2) {
					// Found no true synonym in M that satisfies the relationship with index1, 
					// so we have to delete the row.
					table1->deleteRow(realTableIndex);
					numRowsDeleted++;
				}
			}
			// Override synonym2 in the mSynonymResultsTables to point to this new table
			mSynonymResultsTables[synonym2] = table1;
		}
	}
	


	duration = ( std::clock() - start ) / (double) CLOCKS_PER_SEC;
	//cout << "updateTablesWithNewRelationship() that resulted in a table of numRows = " << mSynonymResultsTables.at(synonym1)->getNumRows()
	//	<< " and numCols = " << mSynonymResultsTables.at(synonym1)->getHeaders().size() << " took " << duration << " seconds\n";



	// Here, we are ensured that we have a table for synonym1.
	// If it is empty it means that we have no possible answers.
	if (mSynonymResultsTables.at(synonym1)->getNumRows() > 0) {
		return true;
	} else {
		return false;
	}
}

//	Copies rows from tableFrom onto this table.
//	Rows to copy should be specified in rowIndexesToCopyFrom.
//	Returns the number of rows duplicated in tableTo during the copying process.
int QueryEvaluator::copyTableRows(Table<string, int>& tableTo, int tableToRowToDuplicate, const Table<string, int>& tableFrom, 
	const std::vector<int>& rowIndexesToCopyFrom) {
		// Ensure that tableToRowToDuplicate exists
		if (tableToRowToDuplicate >= tableTo.getNumRows()) {
			return ERROR_COPYTABLEROWS_ROWTODUPLICATE_DOES_NOT_EXIST; // to indicate error
		}
		if (rowIndexesToCopyFrom.empty()) {
			return -10; // to indicate error (should not call this function without rows to copy from
		}
		int numRowsDuplicated = 0;
		
		// For each row in rowIndexesToCopyFrom, copy it onto tableTo, starting from tableToRowToDuplicate
		int duplicatesRequired = rowIndexesToCopyFrom.size() - 1;
		tableTo.duplicateRow(tableToRowToDuplicate, duplicatesRequired);
		numRowsDuplicated = duplicatesRequired;

		// Insert each column in tableFrom to tableTo
		std::vector<std::string>& tableFromHeaders = tableFrom.getHeaders();
		for (unsigned int i = 0; i < tableFromHeaders.size(); i++) {
			const std::string& header = tableFromHeaders.at(i);
			tableTo.insertColumn(header);
		
			// Ensure that every column has the same length by filling them up with -1
			// before beginning. If columns before then are empty, we insert -1 to fill it up.
			// IF THERE IS -1 IN THE TABLES, IT INDICATES ERROR!!!
			for (int j = tableTo.getColumnSize(header); j < tableTo.getNumRows(); j++) {
				tableTo.appendEntry(header, -1);
			}
		}

		// Now, firstly, copy one row from rowIndexesToCopyFrom onto the tableToRowToDuplicate.
		int rowIndexToCopyFrom = rowIndexesToCopyFrom.at(0);
		// Ensure that this index exists in tableFrom
		if (rowIndexToCopyFrom >= tableFrom.getNumRows() || rowIndexToCopyFrom < 0) {
			return ERROR_COPYTABLEROWS_ROWTOCOPYFROM_DOES_NOT_EXIST; // to indicate error
		}
		// Here, we are ensured that the rowIndexToCopyFrom exists in tableFrom
		// For each of the columns, copy the entry over 1 by 1
		for (unsigned int j = 0; j < tableFromHeaders.size(); j++) {
			const std::string& header = tableFromHeaders.at(j);

			int itemToCopy = tableFrom.getEntry(header, rowIndexToCopyFrom);
			tableTo.modifyEntry(header, tableToRowToDuplicate, itemToCopy);
		}

		for (unsigned int i = 1; i < rowIndexesToCopyFrom.size(); i++) {
			int rowIndexToCopyFrom = rowIndexesToCopyFrom.at(i);
			// Ensure that this index exists in tableFrom
			if (rowIndexToCopyFrom >= tableFrom.getNumRows() || rowIndexToCopyFrom < 0) {
				return ERROR_COPYTABLEROWS_ROWTOCOPYFROM_DOES_NOT_EXIST; // to indicate error
			}
			// Here, we are ensured that the rowIndexToCopyFrom exists in tableFrom
			// For each of the columns, copy the entry over 1 by 1
			for (unsigned int j = 0; j < tableFromHeaders.size(); j++) {
				const std::string& header = tableFromHeaders.at(j);

				int itemToCopy = tableFrom.getEntry(header, rowIndexToCopyFrom);
				tableTo.modifyEntry(header, tableToRowToDuplicate, itemToCopy);
			}
		}

		return numRowsDuplicated;
}


// Evaluates all the with-clauses existing in the mConstraintTable, using the mSynonymResultsTables,
// returning true if ALL constraints evaluated are true, and false if even one constraint is false.
bool QueryEvaluator::evaluateAllWithClausesUsingTable() {
	bool isConstraintTrue = true;
	int numberOfConstraints = mConstraintTable.getNumberOfEntries();
	for (int i = 0; i < numberOfConstraints; i++) {
		ConstraintEntry& constraintEntry = mConstraintTable.getConstraintEntry(i);
		isConstraintTrue = evaluateOneWithClauseUsingTable(constraintEntry);
		if ( !isConstraintTrue) {
			break;
		}
	}
	return isConstraintTrue;
}

// Evaluates one with-clause (ConstraintEntry), using the mSynonymResultsTables,
// and returns true if the constraint is possible, and false if not.
bool QueryEvaluator::evaluateOneWithClauseUsingTable(const ConstraintEntry &constraintEntry) {
	std::string conArg1 = constraintEntry.constraintArguments[0];
	std::string conArg2 = constraintEntry.constraintArguments[1];
	RelationshipArgumentType conArgType1 = constraintEntry.constraintArgumentTypes[0];
	RelationshipArgumentType conArgType2 = constraintEntry.constraintArgumentTypes[1];

	bool isConstraintTrue = true;

	if (isSynonymType(conArgType1) && isSynonymType(conArgType2)) {
		// Both conArg1 and conArg2 are synonyms
		isConstraintTrue = evaluateOneWithClauseWhereBothArgsAreSynonymsUsingTable(constraintEntry);

	} else if (isSynonymType(conArgType1) && !isSynonymType(conArgType2)) {
		// conArg1 is synonym but conArg2 is not synonym
		isConstraintTrue = evaluateOneWithClauseWhereTheLeftArgIsSynonymUsingTable(constraintEntry);

	} else if ( !isSynonymType(conArgType1) && isSynonymType(conArgType2)) {
		// conArg1 is not synonym but conArg2 is synonym
		isConstraintTrue = evaluateOneWithClauseWhereTheRightArgIsSynonymUsingTable(constraintEntry);

	} else {
		// Both conArg1 and conArg2 are NOT synonyms
		isConstraintTrue = evaluateOneWithClauseWhereBothArgsAreNotSynonyms(constraintEntry);
	}

	return isConstraintTrue;
}

// Evaluates one with-clause (ConstraintEntry) that has a synonym on both sides, using the mSynonymResultsTables,
// and returns true if the constraint is possible, and false if not.
bool QueryEvaluator::evaluateOneWithClauseWhereBothArgsAreSynonymsUsingTable(const ConstraintEntry &constraintEntry) {
	ConstraintType conType = constraintEntry.constraintType;
	std::string conArg1 = constraintEntry.constraintArguments[0];
	std::string conArg2 = constraintEntry.constraintArguments[1];
	RelationshipArgumentType conArgType1 = constraintEntry.constraintArgumentTypes[0];
	RelationshipArgumentType conArgType2 = constraintEntry.constraintArgumentTypes[1];
	ConstraintAttrType conAttrType1 = constraintEntry.constraintAttrTypes[0];
	ConstraintAttrType conAttrType2 = constraintEntry.constraintAttrTypes[1];

	bool isConstraintTrue = true;
	
	if (conType == WITH_STRING) {
		// Only one possibility - conAttrType1 will be VAR_NAME or PROC_NAME, and conAttrType2 VAR_NAME or PROC_NAME
		isConstraintTrue = updateTablesWithNewRelationship(conArg1, conArg2, EQUALS_NAME);

	} else if (conType == WITH_INTEGER) {
		// Two possibilities - arg1/arg2 synonym is prog_line then there will be no conAttrType1
		//						arg1/arg2 synonym is something other than prog_line then conAttrType1/conAttrType2 will be VALUE or STMT_INDEX
		isConstraintTrue = updateTablesWithNewRelationship(conArg1, conArg2, EQUALS_INDEX);

	} else {
		// INVALID constraint type, shouldn't be here!
		cout << "Error in QueryEvaluator evaluateOneWithClauseWhereBothArgsAreSynonymsUsingResultGraphTable(): In a conditional branch that we should not be in!\n";
		isConstraintTrue = false;	
	}
	return isConstraintTrue;
}

// Evaluates one with-clause (ConstraintEntry) that has a synonym on the left side, using the mSynonymResultsTables,
// and returns true if the constraint is possible, and false if not.
bool QueryEvaluator::evaluateOneWithClauseWhereTheLeftArgIsSynonymUsingTable(const ConstraintEntry &constraintEntry) {
	ConstraintType conType = constraintEntry.constraintType;
	std::string conArg1 = constraintEntry.constraintArguments[0];
	std::string conArg2 = constraintEntry.constraintArguments[1];
	RelationshipArgumentType conArgType1 = constraintEntry.constraintArgumentTypes[0];
	RelationshipArgumentType conArgType2 = constraintEntry.constraintArgumentTypes[1];
	ConstraintAttrType conAttrType1 = constraintEntry.constraintAttrTypes[0];
	ConstraintAttrType conAttrType2 = constraintEntry.constraintAttrTypes[1];

	bool isConstraintTrue = true;

	if (conType == WITH_STRING) {
		// Only one possibility - conAttrType1 will be VAR_NAME or PROC_NAME
		// Get all the synonym's indexes, convert the given conArg2 to its index form using the pkb,
		// and compare it with each of the synonym's indexes to find the badIndexes to update the ResultGraphTable with
		
		DesignEntityType conArg1SynonymType = mSynonymTable.getDesignEntityType(conArg1);
		std::vector<int>& conArg1Indexes = getResultIndexesFromTable(conArg1);
		int conArg2Index;
		
		if (conArgType1 == SYNONYM_VARIABLE) {
			conArg2Index = mPkb->getVarIndex(conArg2);
		} else if (conArgType1 == SYNONYM_PROCEDURE || conArg1SynonymType == CALL) {
			conArg2Index = mPkb->getProcIndex(conArg2);
		} else {
			// Has to be either VAR_NAME or PROC_NAME, so we shouldn't be here
			cout << "Error in QueryEvaluator evaluateOneWithClauseWhereTheLeftArgIsSynonymUsingResultGraphTable(): In a conditional branch that we should not be in!\n";
			return false;
		}

		IntBoolMap goodIndexesMap;
		for (unsigned int i = 0; i < conArg1Indexes.size(); i++) {
			int conArg1Index = conArg1Indexes.at(i);

			// Indexes to compare might not be the conArg1Index and conArg2Index themselves, 
			// if there is a c.procName in the with-clause
			int indexToCompareForArg1 = conArg1Index;
			if (conArg1SynonymType == CALL) {
				// Special case for cases when c.procName = "YourProc",
				// we need to check if the stmt #conArg1Index calls the conArg2Index
				indexToCompareForArg1 = mPkb->getCalledByLine(conArg1Index);
			}
			
			if (indexToCompareForArg1 == conArg2Index) {
				goodIndexesMap.insert( std::pair<int, bool>(conArg1Index, true) );
			}
		}

		isConstraintTrue = updateTableWithGoodIndexes(conArg1, goodIndexesMap);

	} else if (conType == WITH_INTEGER) {
		// Two possibilities - arg1 synonym is prog_line then there will be no conAttrType1
		//						arg1 synonym is something other than prog_line then conAttrType1 will be VALUE or STMT_INDEX
		// In BOTH cases, get all the synonym's indexes, convert the given conArg2 to integer,
		// and compare it with each of the synonym's indexes to find the badIndexes to update the ResultGraphTable with
		
		DesignEntityType conArg1SynonymType = mSynonymTable.getDesignEntityType(conArg1);
		std::vector<int>& conArg1Indexes = getResultIndexesFromTable(conArg1);
		int conArg2Index = std::stoi(conArg2);

		IntBoolMap goodIndexesMap;
		for (unsigned int i = 0; i < conArg1Indexes.size(); i++) {
			int conArg1Index = conArg1Indexes.at(i);
			if (conArg1Index == conArg2Index) {
				goodIndexesMap.insert( std::pair<int, bool>(conArg1Index, true) );
			}
		}

		isConstraintTrue = updateTableWithGoodIndexes(conArg1, goodIndexesMap);

	} else {
		// INVALID constraint type, shouldn't be here!
		cout << "Error in QueryEvaluator evaluateOneWithClauseWhereTheLeftArgIsSynonymUsingResultGraphTable(): In a conditional branch that we should not be in!\n";
		isConstraintTrue = false;	
	}

	return isConstraintTrue;
}

// Evaluates one with-clause (ConstraintEntry) that has a synonym on the right side, using the mSynonymResultsTables,
// and returns true if the constraint is possible, and false if not.
bool QueryEvaluator::evaluateOneWithClauseWhereTheRightArgIsSynonymUsingTable(const ConstraintEntry &constraintEntry) {
	std::string conArg1 = constraintEntry.constraintArguments[0];
	std::string conArg2 = constraintEntry.constraintArguments[1];
	RelationshipArgumentType conArgType1 = constraintEntry.constraintArgumentTypes[0];
	RelationshipArgumentType conArgType2 = constraintEntry.constraintArgumentTypes[1];
	ConstraintAttrType conAttrType1 = constraintEntry.constraintAttrTypes[0];
	ConstraintAttrType conAttrType2 = constraintEntry.constraintAttrTypes[1];

	bool isConstraintTrue = true;

	// Swap the arg2 and arg1, then run the algorithm where left arg is synonym
	ConstraintEntry swappedConstraintEntry = constraintEntry;
	swappedConstraintEntry.constraintArguments[0] = conArg2;
	swappedConstraintEntry.constraintArguments[1] = conArg1;
	swappedConstraintEntry.constraintArgumentTypes[0] = conArgType2;
	swappedConstraintEntry.constraintArgumentTypes[1] = conArgType1;
	swappedConstraintEntry.constraintAttrTypes[0] = conAttrType2;
	swappedConstraintEntry.constraintAttrTypes[1] = conAttrType1;

	isConstraintTrue = evaluateOneWithClauseWhereTheLeftArgIsSynonymUsingTable(swappedConstraintEntry);

	return isConstraintTrue;
}

// Evaluate all pattern clauses using the mSynonymResultsTables
bool QueryEvaluator::evaluateAllPatternsUsingTable() {
	bool isPatternTrue = true;
	for (int i = 0; i < mPatternTable.getNumberOfEntries(); i++) {
		const PatternEntry& patternEntry = mPatternTable.getPatternEntryAtIndex(i);
		isPatternTrue = evaluateOnePatternUsingTable(patternEntry);
		if ( !isPatternTrue) {
			break;
		}
	}
	return isPatternTrue;
}

bool QueryEvaluator::evaluateOnePatternUsingTable(const PatternEntry& patternEntry) {
	
	bool isPatternTrue = true;

	const std::string& patternSyn = patternEntry.synonym;
	DesignEntityType entType = mSynonymTable.getDesignEntityType(patternSyn);
	PatternType patternType = SpaEnumTranslator::translateDesignEntityTypeToPatternType(entType);
	const std::string& arg1 = patternEntry.args.at(0);
	RelationshipArgumentType arg1SynType = patternEntry.argSynonymTypes.at(0);
	TreeNode* arg2Expr = patternEntry.exprArguments.at(1);
	TreeNode* arg3Expr = patternEntry.exprArguments.at(2);
	bool perfectMatchRequired1 = patternEntry.perfectMatchRequirementVector.at(0);
	bool perfectMatchRequired2 = patternEntry.perfectMatchRequirementVector.at(1);
	bool perfectMatchRequired3 = patternEntry.perfectMatchRequirementVector.at(2);

	// Get the proper varIndexes for arg1 to use for the pattern evaluation loop later.
	if (arg1SynType != INVALID_ARG) {
		// arg1 is a synonym variable! (no other types of synonym is possible for arg1)
		isPatternTrue = evaluateOnePatternWhereArg1IsSynonymUsingTable(patternSyn, patternType,
													arg1, perfectMatchRequired1, arg1SynType, 
													arg2Expr, perfectMatchRequired2, 
													arg3Expr, perfectMatchRequired3);
	} else {
		isPatternTrue = evaluateOnePatternWhereArg1IsNotSynonymUsingTable(patternSyn, patternType,
													arg1, perfectMatchRequired1, arg1SynType, 
													arg2Expr, perfectMatchRequired2, 
													arg3Expr, perfectMatchRequired3);
	}
	return isPatternTrue;
}

// Evaluate one pattern clause using the mSynonymResultsTables
bool QueryEvaluator::evaluateOnePatternUsingTable(std::string patternSyn, PatternType patternType, 
	std::string arg1, bool perfectMatchRequired1, RelationshipArgumentType arg1SynType,
	TreeNode* arg2, bool perfectMatchRequired2, TreeNode* arg3, bool perfectMatchRequired3) {

		bool isPatternTrue = true;
		// Get the proper varIndexes for arg1 to use for the pattern evaluation loop later.
		if (arg1SynType != INVALID_ARG) {
			// arg1 is a synonym variable! (no other types of synonym is possible for arg1)
			isPatternTrue = evaluateOnePatternWhereArg1IsSynonymUsingTable(patternSyn, patternType,
														arg1, perfectMatchRequired1, arg1SynType, 
														arg2, perfectMatchRequired2, 
														arg3, perfectMatchRequired3);
		} else {
			isPatternTrue = evaluateOnePatternWhereArg1IsNotSynonymUsingTable(patternSyn, patternType,
														arg1, perfectMatchRequired1, arg1SynType, 
														arg2, perfectMatchRequired2, 
														arg3, perfectMatchRequired3);
		}
		return isPatternTrue;
}

// Evaluate one pattern clause where arg1 is a synonym using the mSynonymResultsTable
bool QueryEvaluator::evaluateOnePatternWhereArg1IsSynonymUsingTable(std::string patternSyn, PatternType patternType, 
	std::string arg1, bool perfectMatchRequired1, RelationshipArgumentType arg1SynType,
	TreeNode* arg2, bool perfectMatchRequired2,	TreeNode* arg3, bool perfectMatchRequired3) {

		bool isPatternTrue = true;
		// both patternSyn and arg1 are synonyms!
		// have to update mResultGraphTable with relationship between patternSyn and arg1
		if (patternType == PATTERN_ASSIGN) {
			// patternType == assign (e.g. pattern a(v,..))
			// relationship between patternSyn (a) and arg1 (v) is modfies(patternSyn, arg1)
			// so we first evaluate this relationship
			isPatternTrue = updateTablesWithNewRelationship(patternSyn, arg1, MODIFIES_LINE);

			if (isPatternTrue == false) {
				return false;
			}

			// now, we evaluate the pattern
			DesignEntityType arg1EntityType = mSynonymTable.getDesignEntityType(arg1);
			std::vector<int>& arg1Indexes = mSynonymResultsTables.at(arg1)->getColumn(arg1);
			IntBoolMap goodIndexesMap;
			IntBoolMap indexDoneMap;
			for (unsigned int i = 0; i < arg1Indexes.size(); i++) {
				int arg1Index = arg1Indexes.at(i);
				// Don't do the same index twice
				if (Utilities::isKeyInMap_TypeType(indexDoneMap, arg1Index)) {
					continue;
				}
				std::vector<int>& indexesOfPattern = mPkb->getLineIndexForPattern(patternType, arg1Index, arg2, !perfectMatchRequired2);
				for (unsigned int j = 0; j < indexesOfPattern.size(); j++) {
					int goodIndex = indexesOfPattern.at(j);
					goodIndexesMap.insert( std::pair<int, bool>(goodIndex, true) );
				}
				indexDoneMap.insert( std::pair<int, bool>(arg1Index, true) );
			}

			isPatternTrue = updateTableWithGoodIndexes(patternSyn, goodIndexesMap);
		} else {
			// patternType == while OR if (e.g. pattern w(v,..) or pattern if(v,..))
			isPatternTrue = updateTablesWithNewRelationship(patternSyn, arg1, USES_LINE);

			if (isPatternTrue == false) {
				return false;
			}

			IntBoolMap& goodIndexesMap = getVarIndexesOfControlVariablesForWhileOrIfStatementsUsingTable(patternSyn, patternType, arg2, 
																										perfectMatchRequired2);
		
			isPatternTrue = updateTableWithGoodIndexes(arg1, goodIndexesMap);
		}

		return isPatternTrue;
}

// Evaluate one pattern clause where arg1 is not a synonym using the mSynonymResultsTables
bool QueryEvaluator::evaluateOnePatternWhereArg1IsNotSynonymUsingTable(std::string patternSyn, PatternType patternType, 
	std::string arg1, bool perfectMatchRequired1, RelationshipArgumentType arg1SynType,
	TreeNode* arg2, bool perfectMatchRequired2,	TreeNode* arg3, bool perfectMatchRequired3) {

		bool isPatternTrue = true;
		std::vector<int> arg1Indexes;
		// arg1 is '_' or "x"-type of specific variable definition
		if (perfectMatchRequired1 == false || arg1 == "_") {
			// arg1 is '_'
			arg1Indexes = mPkb->getVarIndices();
		} else {
			// arg1 is a "x"-type of specific variable definition
			int varIndex = mPkb->getVarIndex(arg1);
			if (varIndex > 0 ) {
				arg1Indexes.push_back(varIndex);
			}
		}

		// Find the good indexes for patternSyn to update the ResultGraphTable
		IntBoolMap goodIndexesMap;
		for (unsigned int i = 0; i < arg1Indexes.size(); i++) {
			int arg1Index = arg1Indexes.at(i);
			std::vector<int>& indexesOfPattern = mPkb->getLineIndexForPattern(patternType, arg1Index, arg2, !perfectMatchRequired2);
			for (unsigned int j = 0; j < indexesOfPattern.size(); j++) {
				int goodIndex = indexesOfPattern.at(j);
				if ( !Utilities::isKeyInMap_TypeType(goodIndexesMap, goodIndex)) {
					// unique good index, so add it
					goodIndexesMap.insert(std::pair<int, bool>(goodIndex, true));
				}
			}
		}
		isPatternTrue = updateTableWithGoodIndexes(patternSyn, goodIndexesMap);
		return isPatternTrue;
}

// Evaluates all explicit relationship clauses
bool QueryEvaluator::evaluateAllRelationshipClausesUsingTable() {
	// Evaluate all the relationship clauses
	bool isRelationshipTrue = true;
	for (int i = 0; i < mRelationshipClauseTable.getNumberOfEntries(); i++) {
		// Also, currently in this SPA prototype, only need one relationship clause for the query.
		RelationshipEntry relationshipEntry = mRelationshipClauseTable.getRelationshipEntry(i);
	
		// Evaluate one query at a time
		isRelationshipTrue = evaluateOneRelationshipClauseUsingTable(relationshipEntry);
		if (isRelationshipTrue == false) {
			break;
		}
	}
	return isRelationshipTrue;
}

// Evaluate one explicit relationship clause
bool QueryEvaluator::evaluateOneRelationshipClauseUsingTable(const RelationshipEntry &relationshipEntry) {
	RelationshipType relType = relationshipEntry.relationshipType;
	std::string relArg1 = relationshipEntry.relationshipArguments[0];
	std::string relArg2 = relationshipEntry.relationshipArguments[1];
	RelationshipArgumentType argType1 = relationshipEntry.relationshipArgumentTypes[0];
	RelationshipArgumentType argType2 = relationshipEntry.relationshipArgumentTypes[1];

	bool isRelationshipTrue = true;

	if ( !(isSynonymInSynonymTable(relArg1) && (argType1 != STRING)) && !(isSynonymInSynonymTable(relArg2) && (argType2 != STRING))) {
		// both relArg1 and relArg2 are NOT synonyms
		// Since argType1 and argType2 do not give UNDERSCORE but instead the types of synonym the underscores SHOULD be
		// if they were not underscores, we have to check this condition first
			
		isRelationshipTrue = checkIfIsTrueRelationshipForNonSynonyms(relType, relArg1, relArg2, argType1, argType2);

	} else if ((isSynonymInSynonymTable(relArg1) && (argType1 != STRING)) && (isSynonymInSynonymTable(relArg2) && (argType2 != STRING))) {
		// relArg1 and relArg2 are both synonyms
		isRelationshipTrue = updateTablesWithNewRelationship(relArg1, relArg2, relType);

	} else if (isSynonymInSynonymTable(relArg1) && (argType1 != STRING)) {
		// relArg1 is a synonym but relArg2 is not
		// for now, relArg2Indexes can be different types of indexes depending on the relType and the argType2
		std::vector<int> *relArg2Indexes = &fetchAppropriateArg2Indexes(relType, relArg2, argType2);

		IntBoolMap& goodIndexesMap = getIndexesOfSynonym1ThatHaveTrueRelationship(relArg1, *relArg2Indexes, relType);
		isRelationshipTrue = updateTableWithGoodIndexes(relArg1, goodIndexesMap);

	} else {
		// relArg1 is NOT a synonym (single index) but relArg2 is a synonym
		// for now, relArg1Indexes can be different types of indexes depending on the relType and the argType1
		std::vector<int> *relArg1Indexes = &fetchAppropriateArg1Indexes(relType, relArg1, argType1);

		IntBoolMap& goodIndexesMap = getIndexesOfSynonym2ThatHaveTrueRelationship(*relArg1Indexes, relArg2, relType);
		isRelationshipTrue = updateTableWithGoodIndexes(relArg2, goodIndexesMap);
	} 

	return isRelationshipTrue;
}

// Finds all the variable indexes which are used as control variables for while/if statements of the specified whileOrIfSynonym
QueryEvaluator::IntBoolMap& QueryEvaluator::getVarIndexesOfControlVariablesForWhileOrIfStatementsUsingTable(std::string whileOrIfSynonym, PatternType patternType,
	TreeNode *arg2, bool perfectMatchRequired2) {
		// Get all the whileOrIfSynonym indexes
		// Get all varIndexes and, using each index of varIndexes as arg1, 
		// find all the indexes which satisfy the pattern whileOrIfSynonym(arg1, arg2)
		// The controlVariableIndexes are index arg1 whenever the set of indexes satisfying the pattern have even one index which matches
		// the whileOrIfSynonym indexes

		DesignEntityType whileOrIfSynonymEntityType = mSynonymTable.getDesignEntityType(whileOrIfSynonym);
		std::vector<int>& whileOrIfSynonymIndexes = mSynonymResultsTables.at(whileOrIfSynonym)->getColumn(whileOrIfSynonym);

		std::vector<int> arg1Indexes = mPkb->getVarIndices();

		IntBoolMap whileOrIfSynonymIndexMap = convertIntVectorToIntBoolMap(whileOrIfSynonymIndexes); // used for speed checking arg1Indexes against it
		IntBoolMap *controlVariableIndexMap = new IntBoolMap(); 

		// find all arg1Indexes which satisfy the pattern whileOrIfSynonym(arg1, arg2)
		for (unsigned int i = 0; i < arg1Indexes.size(); i++) {
			int arg1Index = arg1Indexes.at(i);
			std::vector<int>& lineIndexesWithCorrectPattern = mPkb->getLineIndexForPattern(patternType, arg1Index, arg2, !perfectMatchRequired2);

			// see if any of these line indexes are any of the whileOrIfSynonymIndexes
			for (unsigned int j = 0; j < lineIndexesWithCorrectPattern.size(); j++) {
				int lineIndexWithCorrectPattern = lineIndexesWithCorrectPattern.at(j);
				if (Utilities::isKeyInMap_TypeType(whileOrIfSynonymIndexMap, lineIndexWithCorrectPattern)) {
					// this means arg1Index is a controlVariableIndex!
					if ( !Utilities::isKeyInMap_TypeType(*controlVariableIndexMap, arg1Index)) {
						// add it if not added before
						controlVariableIndexMap->insert(std::pair<int, bool>(arg1Index, true));
					}
				}
			}
		}

		return *controlVariableIndexMap;
}

// Returns the indexes for synonym1 which have at least one true relationship with any of the indexes in relArg2Indexes
QueryEvaluator::IntBoolMap& QueryEvaluator::getIndexesOfSynonym1ThatHaveTrueRelationship(std::string synonym1, const std::vector<int>& relArg2Indexes, 
	RelationshipType relType) {
		IntBoolMap *goodIndexesMapOfSynonym1 = new IntBoolMap();
		IntBoolMap indexesDoneMap;

		if (mSynonymResultsTables.find(synonym1) != mSynonymResultsTables.end()) {
			// Use the column item count unordered_map because there are no repeated keys, unlike the column
			Table<std::string, int>::ColumnItemCountMap& columnItemCountMap = 
				mSynonymResultsTables.at(synonym1)->getColumnItemCountMap(synonym1);
			// Put each index (key of this count unordered_map) into the synonym1Indexes
			for (auto it = columnItemCountMap.begin(); it != columnItemCountMap.end(); it++) {
				bool isRelationshipTrue = false;
				int synonym1Value = it->first;
				for (unsigned int j = 0; j < relArg2Indexes.size(); j++) {
					if (checkIfIsTrueRelationship(relType, synonym1Value, relArg2Indexes.at(j))) {
						isRelationshipTrue = true;
						break;
					}
				}
				if (isRelationshipTrue) {
					goodIndexesMapOfSynonym1->insert( std::pair<int, bool>(synonym1Value, true) );
				}
			}

		} else {
			std::vector<int> *synonym1Indexes = &getAllIndexes(mSynonymTable.getDesignEntityType(synonym1));

			for (unsigned int i = 0; i < synonym1Indexes->size(); i++) {
				bool isRelationshipTrue = false;
				int synonym1Value = synonym1Indexes->at(i);
				// Don't check the same synonym1Value twice
				if (Utilities::isKeyInMap_TypeType(indexesDoneMap, synonym1Value)) {
					continue;
				}
				for (unsigned int j = 0; j < relArg2Indexes.size(); j++) {
					if (checkIfIsTrueRelationship(relType, synonym1Value, relArg2Indexes.at(j))) {
						isRelationshipTrue = true;
						break;
					}
				}
				if (isRelationshipTrue) {
					goodIndexesMapOfSynonym1->insert( std::pair<int, bool>(synonym1Value, true) );
				}
				indexesDoneMap.insert( std::pair<int, bool>(synonym1Value, true) );
			}
		}

		return *goodIndexesMapOfSynonym1;
}

// Returns the indexes for synonym2 which have at least one true relationship with any of the indexes in relArg1Indexes
QueryEvaluator::IntBoolMap& QueryEvaluator::getIndexesOfSynonym2ThatHaveTrueRelationship(const std::vector<int>& relArg1Indexes, std::string synonym2, 
	RelationshipType relType) {
		IntBoolMap *goodIndexesMapOfSynonym2 = new IntBoolMap();
		IntBoolMap indexesDoneMap;

		if (mSynonymResultsTables.find(synonym2) != mSynonymResultsTables.end()) {
			// Use the column item count unordered_map because there are no repeated keys, unlike the column
			Table<std::string, int>::ColumnItemCountMap& columnItemCountMap = 
				mSynonymResultsTables.at(synonym2)->getColumnItemCountMap(synonym2);
			
			for (auto it = columnItemCountMap.begin(); it != columnItemCountMap.end(); it++) {
				bool isRelationshipTrue = false;
				int synonym2Value = it->first;
				for (unsigned int j = 0; j < relArg1Indexes.size(); j++) {
					if (checkIfIsTrueRelationship(relType, relArg1Indexes.at(j), synonym2Value)) {
						isRelationshipTrue = true;
						break;
					}
				}
				if (isRelationshipTrue) {
					goodIndexesMapOfSynonym2->insert( std::pair<int, bool>(synonym2Value, true) );
				}
			}

		} else {
			std::vector<int> *synonym2Indexes = &getAllIndexes(mSynonymTable.getDesignEntityType(synonym2));
		
			for (unsigned int i = 0; i < synonym2Indexes->size(); i++) {
				bool isRelationshipTrue = false;
				int synonym2Value = synonym2Indexes->at(i);
				// Don't check the same synonym2Value twice
				if (Utilities::isKeyInMap_TypeType(indexesDoneMap, synonym2Value)) {
					continue;
				}
				for (unsigned int j = 0; j < relArg1Indexes.size(); j++) {
					if (checkIfIsTrueRelationship(relType, relArg1Indexes.at(j), synonym2Value)) {
						isRelationshipTrue = true;
						break;
					}
				}
				if (isRelationshipTrue) {
					goodIndexesMapOfSynonym2->insert( std::pair<int, bool>(synonym2Value, true) );
				}
				indexesDoneMap.insert( std::pair<int, bool>(synonym2Value, true) );
			}
		}

		return *goodIndexesMapOfSynonym2;
}

/**--------------------------------------------------------------------
 *
 *
 *	Table-driven evaluation above!
 *
 *
 *---------------------------------------------------------------------*/

// Evaluates all the with-clauses existing in the mConstraintTable, using the mResultGraphTable,
// returning true if ALL constraints evaluated are true, and false if even one constraint is false.
bool QueryEvaluator::evaluateAllWithClausesUsingResultGraphTable() {
	bool isConstraintTrue = true;
	int numberOfConstraints = mConstraintTable.getNumberOfEntries();
	for (int i = 0; i < numberOfConstraints; i++) {
		ConstraintEntry& constraintEntry = mConstraintTable.getConstraintEntry(i);
		isConstraintTrue = evaluateOneWithClauseUsingResultGraphTable(constraintEntry);
		if ( !isConstraintTrue) {
			break;
		}
	}
	return isConstraintTrue;
}

// Evaluates one with-clause (ConstraintEntry), using the mResultGraphTable,
// and returns true if the constraint is possible, and false if not.
bool QueryEvaluator::evaluateOneWithClauseUsingResultGraphTable(const ConstraintEntry &constraintEntry) {
	std::string conArg1 = constraintEntry.constraintArguments[0];
	std::string conArg2 = constraintEntry.constraintArguments[1];
	RelationshipArgumentType conArgType1 = constraintEntry.constraintArgumentTypes[0];
	RelationshipArgumentType conArgType2 = constraintEntry.constraintArgumentTypes[1];

	bool isConstraintTrue = true;

	if (isSynonymType(conArgType1) && isSynonymType(conArgType2)) {
		// Both conArg1 and conArg2 are synonyms
		isConstraintTrue = evaluateOneWithClauseWhereBothArgsAreSynonymsUsingResultGraphTable(constraintEntry);

	} else if (isSynonymType(conArgType1) && !isSynonymType(conArgType2)) {
		// conArg1 is synonym but conArg2 is not synonym
		isConstraintTrue = evaluateOneWithClauseWhereTheLeftArgIsSynonymUsingResultGraphTable(constraintEntry);

	} else if ( !isSynonymType(conArgType1) && isSynonymType(conArgType2)) {
		// conArg1 is not synonym but conArg2 is synonym
		isConstraintTrue = evaluateOneWithClauseWhereTheRightArgIsSynonymUsingResultGraphTable(constraintEntry);

	} else {
		// Both conArg1 and conArg2 are NOT synonyms
		isConstraintTrue = evaluateOneWithClauseWhereBothArgsAreNotSynonyms(constraintEntry);
	}

	return isConstraintTrue;
}

// Evaluates one with-clause (ConstraintEntry) that has a synonym on both sides, using the mResultGraphTable,
// and returns true if the constraint is possible, and false if not.
bool QueryEvaluator::evaluateOneWithClauseWhereBothArgsAreSynonymsUsingResultGraphTable(const ConstraintEntry &constraintEntry) {
	ConstraintType conType = constraintEntry.constraintType;
	std::string conArg1 = constraintEntry.constraintArguments[0];
	std::string conArg2 = constraintEntry.constraintArguments[1];
	RelationshipArgumentType conArgType1 = constraintEntry.constraintArgumentTypes[0];
	RelationshipArgumentType conArgType2 = constraintEntry.constraintArgumentTypes[1];
	ConstraintAttrType conAttrType1 = constraintEntry.constraintAttrTypes[0];
	ConstraintAttrType conAttrType2 = constraintEntry.constraintAttrTypes[1];

	bool isConstraintTrue = true;
	
	if (conType == WITH_STRING) {
		// Only one possibility - conAttrType1 will be VAR_NAME or PROC_NAME, and conAttrType2 VAR_NAME or PROC_NAME
		isConstraintTrue = mResultGraphTable.updateWithNewRelationship(conArg1, conArg2, EQUALS_NAME, mPkb, &mSynonymTable);

	} else if (conType == WITH_INTEGER) {
		// Two possibilities - arg1/arg2 synonym is prog_line then there will be no conAttrType1
		//						arg1/arg2 synonym is something other than prog_line then conAttrType1/conAttrType2 will be VALUE or STMT_INDEX
		isConstraintTrue = mResultGraphTable.updateWithNewRelationship(conArg1, conArg2, EQUALS_INDEX, mPkb, &mSynonymTable);

	} else {
		// INVALID constraint type, shouldn't be here!
		cout << "Error in QueryEvaluator evaluateOneWithClauseWhereBothArgsAreSynonymsUsingResultGraphTable(): In a conditional branch that we should not be in!\n";
		isConstraintTrue = false;	
	}
	return isConstraintTrue;
}

// Evaluates one with-clause (ConstraintEntry) that has a synonym on the left side, using the mResultGraphTable,
// and returns true if the constraint is possible, and false if not.
bool QueryEvaluator::evaluateOneWithClauseWhereTheLeftArgIsSynonymUsingResultGraphTable(const ConstraintEntry &constraintEntry) {
	ConstraintType conType = constraintEntry.constraintType;
	const std::string& conArg1 = constraintEntry.constraintArguments[0];
	const std::string& conArg2 = constraintEntry.constraintArguments[1];
	RelationshipArgumentType conArgType1 = constraintEntry.constraintArgumentTypes[0];
	RelationshipArgumentType conArgType2 = constraintEntry.constraintArgumentTypes[1];
	ConstraintAttrType conAttrType1 = constraintEntry.constraintAttrTypes[0];
	ConstraintAttrType conAttrType2 = constraintEntry.constraintAttrTypes[1];

	bool isConstraintTrue = true;

	if (conType == WITH_STRING) {
		// Only one possibility - conAttrType1 will be VAR_NAME or PROC_NAME
		// Get all the synonym's indexes, convert the given conArg2 to its index form using the pkb,
		// and compare it with each of the synonym's indexes to find the badIndexes to update the ResultGraphTable with
		
		DesignEntityType conArg1SynonymType = mSynonymTable.getDesignEntityType(conArg1);
		std::vector<int>& conArg1Indexes = mResultGraphTable.getResultIndexesForSynonym(conArg1, conArg1SynonymType, mPkb);
		int conArg2Index;

		if (conArgType1 == SYNONYM_VARIABLE) {
			conArg2Index = mPkb->getVarIndex(conArg2);
		} else if (conArgType1 == SYNONYM_PROCEDURE || conArg1SynonymType == CALL) {
			conArg2Index = mPkb->getProcIndex(conArg2);
		} else {
			// Has to be either VAR_NAME or PROC_NAME, so we shouldn't be here
			cout << "Error in QueryEvaluator evaluateOneWithClauseWhereTheLeftArgIsSynonymUsingResultGraphTable(): In a conditional branch that we should not be in!\n";
			return false;
		}

		std::vector<int> badIndexes;
		for (unsigned int i = 0; i < conArg1Indexes.size(); i++) {
			int conArg1Index = conArg1Indexes.at(i);

			// Indexes to compare might not be the conArg1Index and conArg2Index themselves, 
			// if there is a c.procName in the with-clause
			int indexToCompareForArg1 = conArg1Index;
			if (conArg1SynonymType == CALL) {
				// Special case for cases when c.procName = "YourProc",
				// we need to check if the stmt #conArg1Index calls the conArg2Index
				indexToCompareForArg1 = mPkb->getCalledByLine(conArg1Index);
			}
			
			if (indexToCompareForArg1 != conArg2Index) {
				badIndexes.push_back(conArg1Index);
			}
		}

		isConstraintTrue = mResultGraphTable.updateSynonymWithBadResults(conArg1, badIndexes, mPkb, &mSynonymTable);

	} else if (conType == WITH_INTEGER) {
		// Two possibilities - arg1 synonym is prog_line then there will be no conAttrType1
		//						arg1 synonym is something other than prog_line then conAttrType1 will be VALUE or STMT_INDEX
		// In BOTH cases, get all the synonym's indexes, convert the given conArg2 to integer,
		// and compare it with each of the synonym's indexes to find the badIndexes to update the ResultGraphTable with
		
		DesignEntityType conArg1SynonymType = mSynonymTable.getDesignEntityType(conArg1);
		std::vector<int>& conArg1Indexes = mResultGraphTable.getResultIndexesForSynonym(conArg1, conArg1SynonymType, mPkb);
		int conArg2Index = std::stoi(conArg2);

		std::vector<int> badIndexes;
		for (unsigned int i = 0; i < conArg1Indexes.size(); i++) {
			int conArg1Index = conArg1Indexes.at(i);
			if (conArg1Index != conArg2Index) {
				badIndexes.push_back(conArg1Index);
			}
		}

		isConstraintTrue = mResultGraphTable.updateSynonymWithBadResults(conArg1, badIndexes, mPkb, &mSynonymTable);

	} else {
		// INVALID constraint type, shouldn't be here!
		cout << "Error in QueryEvaluator evaluateOneWithClauseWhereTheLeftArgIsSynonymUsingResultGraphTable(): In a conditional branch that we should not be in!\n";
		isConstraintTrue = false;	
	}

	return isConstraintTrue;
}

// Evaluates one with-clause (ConstraintEntry) that has a synonym on the right side, using the mResultGraphTable,
// and returns true if the constraint is possible, and false if not.
bool QueryEvaluator::evaluateOneWithClauseWhereTheRightArgIsSynonymUsingResultGraphTable(const ConstraintEntry &constraintEntry) {
	const std::string& conArg1 = constraintEntry.constraintArguments[0];
	const std::string& conArg2 = constraintEntry.constraintArguments[1];
	RelationshipArgumentType conArgType1 = constraintEntry.constraintArgumentTypes[0];
	RelationshipArgumentType conArgType2 = constraintEntry.constraintArgumentTypes[1];
	ConstraintAttrType conAttrType1 = constraintEntry.constraintAttrTypes[0];
	ConstraintAttrType conAttrType2 = constraintEntry.constraintAttrTypes[1];

	bool isConstraintTrue = true;

	// Swap the arg2 and arg1, then run the algorithm where left arg is synonym
	ConstraintEntry swappedConstraintEntry = constraintEntry;
	swappedConstraintEntry.constraintArguments[0] = conArg2;
	swappedConstraintEntry.constraintArguments[1] = conArg1;
	swappedConstraintEntry.constraintArgumentTypes[0] = conArgType2;
	swappedConstraintEntry.constraintArgumentTypes[1] = conArgType1;
	swappedConstraintEntry.constraintAttrTypes[0] = conAttrType2;
	swappedConstraintEntry.constraintAttrTypes[1] = conAttrType1;

	isConstraintTrue = evaluateOneWithClauseWhereTheLeftArgIsSynonymUsingResultGraphTable(swappedConstraintEntry);

	return isConstraintTrue;
}

// Evaluates one with-clause (ConstraintEntry) that has no synonyms on either side, using the mResultGraphTable,
// and returns true if the constraint is possible, and false if not.
bool QueryEvaluator::evaluateOneWithClauseWhereBothArgsAreNotSynonyms(const ConstraintEntry &constraintEntry) {
	const std::string& conArg1 = constraintEntry.constraintArguments[0];
	const std::string& conArg2 = constraintEntry.constraintArguments[1];
	
	// No synonyms, so just compare the strings directly
	bool isConstraintTrue = (conArg1 == conArg2);
	return isConstraintTrue;
}

bool QueryEvaluator::evaluateAllPatternsUsingResultGraphTable() {
	bool isPatternTrue = true;
	for (int i = 0; i < mPatternTable.getNumberOfEntries(); i++) {
		const PatternEntry& patternEntry = mPatternTable.getPatternEntryAtIndex(i);
		isPatternTrue = evaluateOnePatternUsingResultGraphTable(patternEntry);
		if ( !isPatternTrue) {
			break;
		}
	}
	return isPatternTrue;
}

bool QueryEvaluator::evaluateOnePatternUsingResultGraphTable(const PatternEntry& patternEntry) {

		bool isPatternTrue = true;

		const std::string& patternSyn = patternEntry.synonym;
		DesignEntityType entType = mSynonymTable.getDesignEntityType(patternSyn);
		PatternType patternType = patternEntry.patternType;
		const std::string& arg1 = patternEntry.args.at(0);
		RelationshipArgumentType arg1SynType = patternEntry.argSynonymTypes.at(0);
		TreeNode* arg2Expr = patternEntry.exprArguments.at(1);
		TreeNode* arg3Expr = patternEntry.exprArguments.at(2);
		bool perfectMatchRequired1 = patternEntry.perfectMatchRequirementVector.at(0);
		bool perfectMatchRequired2 = patternEntry.perfectMatchRequirementVector.at(1);
		bool perfectMatchRequired3 = patternEntry.perfectMatchRequirementVector.at(2);

		// Get the proper varIndexes for arg1 to use for the pattern evaluation loop later.
		if (arg1SynType != INVALID_ARG) {
			// arg1 is a synonym variable! (no other types of synonym is possible for arg1)
			isPatternTrue = evaluateOnePatternWhereArg1IsSynonymUsingResultGraphTable(patternSyn, patternType,
														arg1, perfectMatchRequired1, arg1SynType, 
														arg2Expr, perfectMatchRequired2, 
														arg3Expr, perfectMatchRequired3);
		} else {
			isPatternTrue = evaluateOnePatternWhereArg1IsNotSynonymUsingResultGraphTable(patternSyn, patternType,
														arg1, perfectMatchRequired1, arg1SynType, 
														arg2Expr, perfectMatchRequired2, 
														arg3Expr, perfectMatchRequired3);
		}
		return isPatternTrue;
}

bool QueryEvaluator::evaluateOnePatternWhereArg1IsSynonymUsingResultGraphTable(std::string patternSyn, PatternType patternType, 
	std::string arg1, bool perfectMatchRequired1, RelationshipArgumentType arg1SynType,
	TreeNode* arg2, bool perfectMatchRequired2,	TreeNode* arg3, bool perfectMatchRequired3) {

		bool isPatternTrue = true;
		// both patternSyn and arg1 are synonyms!
		// have to update mResultGraphTable with relationship between patternSyn and arg1
		if (patternType == PATTERN_ASSIGN) {
			// patternType == assign (e.g. pattern a(v,..))
			// relationship between patternSyn (a) and arg1 (v) is modfies(patternSyn, arg1)

			isPatternTrue = mResultGraphTable.updateWithNewRelationship(patternSyn, arg1, MODIFIES_LINE, mPkb, &mSynonymTable);

			if (isPatternTrue == false) {
				return false;
			}

			// now evaluate the pattern
			DesignEntityType arg1EntityType = mSynonymTable.getDesignEntityType(arg1);
			std::vector<int>& arg1Indexes = mResultGraphTable.getResultIndexesForSynonym(arg1, arg1EntityType, mPkb);
			std::vector<int> goodIndexes;
			std::unordered_map<int, bool> indexMap;
			for (unsigned int i = 0; i < arg1Indexes.size(); i++) {
				int arg1Index = arg1Indexes.at(i);
				std::vector<int>& indexesOfPattern = mPkb->getLineIndexForPattern(patternType, arg1Index, arg2, !perfectMatchRequired2);
				for (unsigned int j = 0; j < indexesOfPattern.size(); j++) {
					int goodIndex = indexesOfPattern.at(j);
					if ( !Utilities::isKeyInMap_TypeType(indexMap, goodIndex)) {
						// unique good index, so add it
						goodIndexes.push_back(goodIndex);
						indexMap.insert(std::pair<int, bool>(goodIndex, true));
					}
				}
			}

			isPatternTrue = mResultGraphTable.updateSynonymWithGoodResults(patternSyn, goodIndexes, mPkb, &mSynonymTable);
		} else {
			// patternType == while OR if (e.g. pattern w(v,..) or pattern if(v,..))
			//std::vector<int>& controlVarIndexes = getVarIndexesOfControlVariablesForWhileOrIfStatements(patternSyn, patternType, arg2, 
			//																							perfectMatchRequired2);

			mResultGraphTable.updateWithNewRelationship(patternSyn, arg1, CONTROL_VARIABLE, mPkb, &mSynonymTable);
			//mResultGraphTable.updateWithNewRelationship(patternSyn, arg1, USES_LINE, mPkb, &mSynonymTable);
			//isPatternTrue = mResultGraphTable.updateSynonymWithGoodResults(arg1, controlVarIndexes, mPkb, &mSynonymTable);
		}

		return isPatternTrue;
}

bool QueryEvaluator::evaluateOnePatternWhereArg1IsNotSynonymUsingResultGraphTable(std::string patternSyn, PatternType patternType, 
	std::string arg1, bool perfectMatchRequired1, RelationshipArgumentType arg1SynType,
	TreeNode* arg2, bool perfectMatchRequired2,	TreeNode* arg3, bool perfectMatchRequired3) {

		bool isPatternTrue = true;
		std::vector<int> arg1Indexes;
		// arg1 is '_' or "x"-type of specific variable definition
		if (perfectMatchRequired1 == false || arg1 == "_") {
			// arg1 is '_'
			arg1Indexes = mPkb->getVarIndices();
		} else {
			// arg1 is a "x"-type of specific variable definition
			int varIndex = mPkb->getVarIndex(arg1);
			if (varIndex > 0 ) {
				arg1Indexes.push_back(varIndex);
			}
		}

		// Find the good indexes for patternSyn to update the ResultGraphTable
		std::vector<int> goodIndexes;
		std::unordered_map<int, bool> indexMap; // so that we add unique indexes to the goodIndexes only
		for (unsigned int i = 0; i < arg1Indexes.size(); i++) {
			int arg1Index = arg1Indexes.at(i);
			std::vector<int>& indexesOfPattern = mPkb->getLineIndexForPattern(patternType, arg1Index, arg2, !perfectMatchRequired2);
			for (unsigned int j = 0; j < indexesOfPattern.size(); j++) {
				int goodIndex = indexesOfPattern.at(j);
				if ( !Utilities::isKeyInMap_TypeType(indexMap, goodIndex)) {
					// unique good index, so add it
					goodIndexes.push_back(goodIndex);
					indexMap.insert(std::pair<int, bool>(goodIndex, true));
				}
			}
		}
		isPatternTrue = mResultGraphTable.updateSynonymWithGoodResults(patternSyn, goodIndexes, mPkb, &mSynonymTable);
		return isPatternTrue;
}

bool QueryEvaluator::evaluateAllRelationshipClausesUsingResultGraphTable() {
	// Evaluate all the relationship clauses
	bool isRelationshipTrue = true;
	for (int i = 0; i < mRelationshipClauseTable.getNumberOfEntries(); i++) {
		RelationshipEntry relationshipEntry = mRelationshipClauseTable.getRelationshipEntry(i);
	
		// Evaluate one query at a time
		isRelationshipTrue = evaluateOneRelationshipClauseUsingResultGraphTable(relationshipEntry);
		if (isRelationshipTrue == false) {
			break;
		}
	}
	return isRelationshipTrue;
}

bool QueryEvaluator::evaluateOneRelationshipClauseUsingResultGraphTable(const RelationshipEntry &relationshipEntry) {
	RelationshipType relType = relationshipEntry.relationshipType;
	const std::string& relArg1 = relationshipEntry.relationshipArguments[0];
	const std::string& relArg2 = relationshipEntry.relationshipArguments[1];
	RelationshipArgumentType argType1 = relationshipEntry.relationshipArgumentTypes[0];
	RelationshipArgumentType argType2 = relationshipEntry.relationshipArgumentTypes[1];

	bool isRelationshipTrue = true;

	if ( !(isSynonymInSynonymTable(relArg1) && (argType1 != STRING)) && !(isSynonymInSynonymTable(relArg2) && (argType2 != STRING))) {
		// both relArg1 and relArg2 are NOT synonyms
		// Since argType1 and argType2 do not give UNDERSCORE but instead the types of synonym the underscores SHOULD be
		// if they were not underscores, we have to check this condition first
		isRelationshipTrue = checkIfIsTrueRelationshipForNonSynonyms(relType, relArg1, relArg2, argType1, argType2);

	} else if ( (isSynonymInSynonymTable(relArg1) && (argType1 != STRING)) && !(isSynonymInSynonymTable(relArg2) && (argType2 != STRING))) {
		// relArg1 is a synonym but relArg2 is not
		// relArg2Indexes can be different types of indexes depending on the relationship and argType.
		std::vector<int> *relArg2Indexes = &fetchAppropriateArg2Indexes(relType, relArg2, argType2);
		
		std::vector<int>& badIndexesOfSynonym1 = getIndexesOfSynonym1ThatHaveNoTrueRelationship(relArg1, *relArg2Indexes, relType);
		isRelationshipTrue = mResultGraphTable.updateSynonymWithBadResults(relArg1, badIndexesOfSynonym1, mPkb, &mSynonymTable);
	
	} else if ( !(isSynonymInSynonymTable(relArg1) && (argType1 != STRING)) && (isSynonymInSynonymTable(relArg2) && (argType2 != STRING))) {
		// relArg1 is NOT a synonym (single index) but relArg2 is a synonym
		// relArg1Indexes can be different types of indexes depending on the relationship and argType.
		std::vector<int> *relArg1Indexes = &fetchAppropriateArg1Indexes(relType, relArg1, argType1);

		std::vector<int>& badIndexesOfSynonym2 = getIndexesOfSynonym2ThatHaveNoTrueRelationship(*relArg1Indexes, relArg2, relType);
		isRelationshipTrue = mResultGraphTable.updateSynonymWithBadResults(relArg2, badIndexesOfSynonym2, mPkb, &mSynonymTable);

	} else {
		// relArg1 and relArg2 are both synonyms
		isRelationshipTrue = mResultGraphTable.updateWithNewRelationship(relArg1, relArg2, relType, mPkb, &mSynonymTable);
	}

	return isRelationshipTrue;
}

std::vector<int>& QueryEvaluator::fetchAppropriateArg1Indexes(RelationshipType relType, std::string relArg1, RelationshipArgumentType argType1) {
	std::vector<int> *relArg1Indexes = NULL;
	switch (relType) {
	case MODIFIES_PROC:
		// Fallthrough
	case USES_PROC:
		// Fallthrough
	case CALLS:
		// Fallthrough
	case CALLS_STAR:
		relArg1Indexes = &fetchProcIndexesForNonSynonym(relArg1, argType1);
		break;
	default:
		relArg1Indexes = &fetchStmtIndexesForNonSynonym(relArg1, argType1);
		break;
	}
	return *relArg1Indexes;
}

vector<int>& QueryEvaluator::fetchAppropriateArg2Indexes(RelationshipType relType, std::string relArg2, RelationshipArgumentType argType2) {
	std::vector<int> *relArg2Indexes = NULL;
	switch (relType) {
	case MODIFIES_LINE:
		// Fallthrough
	case MODIFIES_PROC:
		// Fallthrough
	case USES_LINE:
		// Fallthrough
	case USES_PROC:
		relArg2Indexes = &fetchVariableIndexesForNonSynonym(relArg2, argType2);
		break;
	case CALLS:
		// Fallthrough
	case CALLS_STAR:
		relArg2Indexes = &fetchProcIndexesForNonSynonym(relArg2, argType2);
		break;
	default:
		relArg2Indexes = &fetchStmtIndexesForNonSynonym(relArg2, argType2);
		break;
	}
	return *relArg2Indexes;
}
vector<int>& QueryEvaluator::fetchStmtIndexes(std::string relArg, RelationshipArgumentType argType) {
	if (mMapOfSynonymToIntegerResults.find(relArg) != mMapOfSynonymToIntegerResults.end()
		&& isSynonymType(argType) && relArg != "_") {
		// relArg already has answers, and is a synonym type that is NOT an underscore (valid synonym)
		return mMapOfSynonymToIntegerResults.at(relArg);
	}

	vector<int> *indexes = new std::vector<int>();
	// Noting that argType might be of INTEGER (meaning stmt#), we need to check it.
	if (argType == INTEGER) {
		// In this case, relArg is the ONLY index that should be in the vector returned
		int index = std::stoi(relArg);
		indexes->push_back( index );
	} else {
		// Otherwise, translate to entity type to fetch the vector of indexes from PKB
		DesignEntityType entityType = SpaEnumTranslator::translateRelationshipArgTypeToDesignEntityType(argType);
		indexes = &getIndexesOfEntityType(entityType);
	}
	return *indexes;
}

std::vector<int>& QueryEvaluator::fetchStmtIndexesForNonSynonym(std::string relArg, RelationshipArgumentType argType) {
	std::vector<int> *indexes = new std::vector<int>();
	// Noting that argType might be of INTEGER (meaning stmt#), we need to check it.
	if (argType == INTEGER) {
		// In this case, relArg is the ONLY index that should be in the vector returned
		int index = std::stoi(relArg);
		indexes->push_back( index );
	} else {
		// Otherwise, translate to entity type to fetch the vector of indexes from PKB
		DesignEntityType entityType = SpaEnumTranslator::translateRelationshipArgTypeToDesignEntityType(argType);
		indexes = &getIndexesOfEntityType(entityType);
	}
	return *indexes;
}

std::vector<int>& QueryEvaluator::fetchProcIndexesForNonSynonym(std::string relArg, RelationshipArgumentType argType) {
	std::vector<int> *indexes = new std::vector<int>();
	// Noting that argType might be of STRING (meaning name of procedure), we need to check it.
	if (argType == STRING) {
		// In this case, relArg is the name of a procedure,
		// so we look up the procedure index from the PKB and that index should be the only index in the vector returned.
		int index = mPkb->getProcIndex(relArg);
		indexes->push_back(index);
	} else {
		// Otherwise, translate to entity type to fetch the vector of indexes from PKB
		DesignEntityType entityType = SpaEnumTranslator::translateRelationshipArgTypeToDesignEntityType(argType);
		indexes = &getIndexesOfEntityType(entityType);
	}
	return *indexes;
}

std::vector<int>& QueryEvaluator::fetchAssignIndexesForNonSynonym(std::string relArg, RelationshipArgumentType argType) {
	std::vector<int> *indexes = new std::vector<int>();
	// Noting that argType might be of INTEGER (meaning assign#), we need to check it.
	if (argType == INTEGER) {
		// In this case, relArg is the ONLY index that should be in the vector returned
		int index = std::stoi(relArg);
		if (mPkb->isLineEntity(index, Type::Entity::ASSIGNMENT_LINE_ENTITY)) {
			indexes->push_back( index );
		}
	} else {
		// Otherwise, translate to entity type to fetch the vector of assign indexes from PKB
		indexes = &getIndexesOfEntityType(ASSIGN);
	}
	return *indexes;
}

std::vector<int>& QueryEvaluator::fetchVariableIndexes(std::string relArg, RelationshipArgumentType argType) {
	vector<int> *indexes = new std::vector<int>();
	if (mMapOfSynonymToIntegerResults.find(relArg) != mMapOfSynonymToIntegerResults.end()
		&& isSynonymType(argType) && relArg != "_") {
		// relArg already has answers, and is a synonym type that is NOT an underscore (valid synonym)
		*indexes = mMapOfSynonymToIntegerResults.at(relArg);
		return *indexes;
	}

	// Noting that argType might be of STRING (meaning a specific variable definition), we need to check it.
	if (argType == STRING) {
		// In this case, relArg is the ONLY index that should be in the vector returned
		int varIndex = mPkb->getVarIndex(relArg);
		if (varIndex > 0) {
			indexes->push_back( varIndex );
		}
	} else if (argType == SYNONYM_VARIABLE) {
		// fetch all variable indexes from the pkbs
		*indexes = mPkb->getVarIndices();
	}
	return *indexes;
}

std::vector<int>& QueryEvaluator::fetchVariableIndexesForNonSynonym(std::string relArg, RelationshipArgumentType argType) {
	std::vector<int> *indexes = new std::vector<int>();
	// Noting that argType might be of STRING (meaning a specific variable definition), we need to check it.
	if (argType == STRING) {
		// In this case, relArg is the ONLY index that should be in the vector returned
		int varIndex = mPkb->getVarIndex(relArg);
		if (varIndex > 0) {
			indexes->push_back( varIndex );
		}
	} else {
		// fetch all variable indexes from the pkbs
		*indexes = mPkb->getVarIndices();
	}
	return *indexes;
}

// Finds all the variable indexes which are used as control variables for while/if statements of the specified whileOrIfSynonym
std::vector<int>& QueryEvaluator::getVarIndexesOfControlVariablesForWhileOrIfStatements(std::string whileOrIfSynonym, PatternType patternType,
	TreeNode *arg2, bool perfectMatchRequired2) {
		// Get all the whileOrIfSynonym indexes
		// Get all varIndexes and, using each index of varIndexes as arg1, 
		// find all the indexes which satisfy the pattern whileOrIfSynonym(arg1, arg2)
		// The controlVariableIndexes are index arg1 whenever the set of indexes satisfying the pattern have even one index which matches
		// the whileOrIfSynonym indexe

		std::vector<int> *controlVariableIndexes = new std::vector<int>();

		DesignEntityType whileOrIfSynonymEntityType = mSynonymTable.getDesignEntityType(whileOrIfSynonym);
		std::vector<int>& whileOrIfSynonymIndexes = mResultGraphTable.getResultIndexesForSynonym(whileOrIfSynonym, whileOrIfSynonymEntityType, mPkb);

		std::vector<int> arg1Indexes = mPkb->getVarIndices();

		IntBoolMap whileOrIfSynonymIndexMap; // used for speed checking arg1Indexes against it
		IntBoolMap controlVariableIndexMap; // used to ensure uniqueness when adding controlVariableIndexes
		
		// initialize the whileOrIfSynonymIndexMap
		for (unsigned int i = 0; i < whileOrIfSynonymIndexes.size(); i++) {
			whileOrIfSynonymIndexMap.insert(std::pair<int, bool>(whileOrIfSynonymIndexes.at(i), true));
		}

		// find all arg1Indexes which satisfy the pattern whileOrIfSynonym(arg1, arg2)
		for (unsigned int i = 0; i < arg1Indexes.size(); i++) {
			int arg1Index = arg1Indexes.at(i);
			std::vector<int>& lineIndexesWithCorrectPattern = mPkb->getLineIndexForPattern(patternType, arg1Index, arg2, !perfectMatchRequired2);

			// see if any of these line indexes are any of the whileOrIfSynonymIndexes
			for (unsigned int j = 0; j < lineIndexesWithCorrectPattern.size(); j++) {
				int lineIndexWithCorrectPattern = lineIndexesWithCorrectPattern.at(j);
				if (Utilities::isKeyInMap_TypeType(whileOrIfSynonymIndexMap, lineIndexWithCorrectPattern)) {
					// this means arg1Index is a controlVariableIndex!
					if ( !Utilities::isKeyInMap_TypeType(controlVariableIndexMap, arg1Index)) {
						// add it if not added before
						controlVariableIndexes->push_back(arg1Index);
						controlVariableIndexMap.insert(std::pair<int, bool>(arg1Index, true));
					}
				}
			}
		}

		return *controlVariableIndexes;
}

std::vector<string>& QueryEvaluator::convertIntegerVectorToStringVector(const vector<int>& integers) {
	vector<string> *strings = new vector<string>();
	for (unsigned int i = 0; i < integers.size(); i++) {
		int integer = integers.at(i);
		std::string str = convertIntegerToString(integer);
		strings->push_back(str);
	}
	return *strings;
}

std::vector<string>& QueryEvaluator::translateIndexesToVariableNames(const std::vector<int>& variableIndexes) {
	std::vector<string> *results = new std::vector<string>();
	for (unsigned int i = 0; i < variableIndexes.size(); i++) {
		int varIndex = variableIndexes.at(i);
		std::string varName = mPkb->getVarName(varIndex);
		results->push_back(varName);
	}
	return *results;
}

std::vector<string>& QueryEvaluator::translateIndexesToProcNames(const std::vector<int>& procIndexes) {
	std::vector<string> *results = new std::vector<string>();
	for (unsigned int i = 0; i < procIndexes.size(); i++) {
		int procIndex = procIndexes.at(i);
		std::string procName = mPkb->getProcName(procIndex);
		results->push_back(procName);
	}
	return *results;
}

std::vector<string>& QueryEvaluator::translateCallIndexesToCalledProcNames(const std::vector<int> &callIndexes) {
	std::vector<string> *results = new std::vector<string>();
	std::unordered_map<string, bool> resultsAddedMap; // for uniqueness
	for (unsigned int i = 0; i < callIndexes.size(); i++) {
		int callIndex = callIndexes.at(i);
		std::string procName = mPkb->getProcName(mPkb->getCalledByLine(callIndex));
		if ( !Utilities::isKeyInMap_TypeType(resultsAddedMap, procName)) {
			results->push_back(procName);
			resultsAddedMap.insert( std::make_pair(procName, true) );
		}
	}
	return *results;
}

void QueryEvaluator::sortIntegerVector(vector<int> *vect) {
	struct IntComparator {
			bool operator() (int i,int j) { return (i<j);}
	} myIntComparator;
	std::sort(vect->begin(), vect->end(), myIntComparator);
}

std::vector<int>& QueryEvaluator::validateResultIndexes(const vector<int>& resultIndexes, DesignEntityType synonymType) {
	std::vector<int> *validatedResultIndexes = new std::vector<int>();
	std::vector<int> *indexesOfSynonymType = NULL; // to validate that the index is equal to synonymType
	std::unordered_map<int, int> uniqueIndexesMap; // to ensure unique indexes
	
	Type::Entity::Line lineEntity;
	switch (synonymType) {
	case CONSTANT:
		*indexesOfSynonymType = mPkb->getConstants();
		break;
	case VARIABLE:
		*indexesOfSynonymType = mPkb->getVarIndices();
		break;
	case PROCEDURE:
		*indexesOfSynonymType = mPkb->getProcIndices();
		break;
	default:
		lineEntity = SpaEnumTranslator::translateDesignEntityTypeToTypeEntityLine(synonymType);
		*indexesOfSynonymType = mPkb->getLinesByEntity(lineEntity);
		break;
	}

	for (unsigned int i = 0; i < resultIndexes.size(); i++) {
		int currentIndex = resultIndexes.at(i);
		if ( currentIndex <= 0 && (synonymType != CONSTANT) ) {
			// invalid index, so just go to next index immediately
			continue;
		}
		if ( !Utilities::isKeyInMap_TypeType(uniqueIndexesMap, currentIndex) && Utilities::isExistInList(*indexesOfSynonymType, currentIndex)) {
			// unique and valid index, so add it!
			uniqueIndexesMap.insert( std::pair<int, int>(currentIndex, currentIndex) );
			validatedResultIndexes->push_back(currentIndex);
		}
	}

	sortIntegerVector(validatedResultIndexes);

	return *validatedResultIndexes;
}

std::vector<int>& QueryEvaluator::getIndexesOfEntityType(DesignEntityType synEntityType) {

	std::vector<int> *resultIndexes = new std::vector<int>();
	switch (synEntityType) {
	case CONSTANT:
		*resultIndexes = mPkb->getConstants();
		break;
	case VARIABLE:
		*resultIndexes = mPkb->getVarIndices();
		break;
	case PROCEDURE:
		*resultIndexes = mPkb->getProcIndices();
		break;
	default:
		Type::Entity::Line lineEntity;
		lineEntity = SpaEnumTranslator::translateDesignEntityTypeToTypeEntityLine(synEntityType);
		*resultIndexes = mPkb->getLinesByEntity(lineEntity);
		break;
	}
	return *resultIndexes;
}

std::vector<string>& QueryEvaluator::getResultsOfEntityTypeInStrings(DesignEntityType synEntityType) {
	std::vector<string> *results = new std::vector<string>();
	std::vector<int> *intResults = NULL;
	switch (synEntityType) {
	case CONSTANT:
		*intResults = mPkb->getConstants();
		*results = convertIntegerVectorToStringVector(*intResults);
		break;
	case VARIABLE:
		*intResults = mPkb->getVarIndices();
		*results = translateIndexesToVariableNames(*intResults);
		break;
	case PROCEDURE:
		*intResults = mPkb->getProcIndices();
		*results = translateIndexesToProcNames(*intResults);
		break;
	default:
		Type::Entity::Line lineEntity;
		lineEntity = SpaEnumTranslator::translateDesignEntityTypeToTypeEntityLine(synEntityType);

		*intResults = mPkb->getLinesByEntity(lineEntity);
		*results = convertIntegerVectorToStringVector(*intResults);
		break;
	}
	return *results;
}

std::vector<int>& QueryEvaluator::getResultIndexesFromTable(std::string synonym) {
	std::vector<int> *resultIndexes = NULL;
	if (mSynonymResultsTables.find(synonym) == mSynonymResultsTables.end()) {
		resultIndexes = &getAllIndexes(mSynonymTable.getDesignEntityType(synonym));

	} else {
		resultIndexes = new std::vector<int>();
		// This item count unordered_map will contain no duplicate items as keys
		Table<std::string, int>::ColumnItemCountMap& columnItemCountMap = 
			mSynonymResultsTables.at(synonym)->getColumnItemCountMap(synonym); 
		// Insert each key in this count unordered_map into the resultIndexes
		for (auto it = columnItemCountMap.begin(); it != columnItemCountMap.end(); it++) {
			resultIndexes->push_back(it->first);
		}
	}
	return *resultIndexes;
}

std::vector<string>& QueryEvaluator::getResultStringsFromTable(std::string synonym, ConstraintAttrType synAttrType, DesignEntityType synEntityType) {
	// If synonym does not have a table for itself, then return all possible indexes for it.
	std::vector<int> *resultIndexes = NULL;
	if (mSynonymResultsTables.find(synonym) == mSynonymResultsTables.end()) {
		resultIndexes = &getAllIndexes(synEntityType);
	} else {
		resultIndexes = &getResultIndexesFromTable(synonym);
	}
	std::vector<string> *results = new std::vector<string>();

	switch (synEntityType) {
	case VARIABLE: // variables need their indexes translated through the PKB
		*results = translateIndexesToVariableNames(*resultIndexes);
		break;
	case PROCEDURE: // procedures need their indexes translated through the PKB
		*results = translateIndexesToProcNames(*resultIndexes);
		break;
	case CALL: // calls may need their indexes translated into the proc names they call
		if (synAttrType == PROC_NAME) {
			*results = translateCallIndexesToCalledProcNames(*resultIndexes);
		} else {
			*results = convertIntegerVectorToStringVector(*resultIndexes);
		}
		break;
	default: // everything else can be translated from integer to string directly
		*results = convertIntegerVectorToStringVector(*resultIndexes);
		break;
	}

	return *results;
}

std::vector<string>& QueryEvaluator::getResultStringsFromResultGraphTable(std::string synonym, ConstraintAttrType synAttrType, DesignEntityType synEntityType) {
	std::vector<int> &resultIndexes = mResultGraphTable.getResultIndexesForSynonym(synonym, synEntityType, mPkb);
	std::vector<string> *results = new std::vector<string>();

	switch (synEntityType) {
	case VARIABLE: // variables need their indexes translated through the PKB
		*results = translateIndexesToVariableNames(resultIndexes);
		break;
	case PROCEDURE: // procedures need their indexes translated through the PKB
		*results = translateIndexesToProcNames(resultIndexes);
		break;
	case CALL: // calls may need their indexes translated into the proc names they call
		if (synAttrType == PROC_NAME) {
			*results = translateCallIndexesToCalledProcNames(resultIndexes);
		} else {
			*results = convertIntegerVectorToStringVector(resultIndexes);
		}
		break;
	default: // everything else can be translated from integer to string directly
		*results = convertIntegerVectorToStringVector(resultIndexes);
		break;
	}

	return *results;
}

bool QueryEvaluator::isSynonymType(RelationshipArgumentType argType) {

	switch (argType) {
	case INTEGER:
		// Fallthrough
	case INVALID_ARG:
		// Fallthrough
	case STRING:
		// Fallthrough
	case UNDERSCORE:
		return false;
		break;
	default:
		return true;
		break;
	}
}

// Returns true if the relationship of relType is true for (synonym1Value, synonym2Value), false otherwise
bool QueryEvaluator::checkIfIsTrueRelationship(RelationshipType relType, int synonym1Value, int synonym2Value) {
	bool isRelationshipTrue = false;
	switch (relType) {
	case MODIFIES_LINE:
		isRelationshipTrue = mPkb->isLineModifies(synonym1Value, synonym2Value);
		break;
	case MODIFIES_PROC:
		isRelationshipTrue = mPkb->isProcModifies(synonym1Value, synonym2Value);
		break;
	case USES_LINE:
		isRelationshipTrue = mPkb->isLineUses(synonym1Value, synonym2Value);
		break;
	case USES_PROC:
		isRelationshipTrue = mPkb->isProcUses(synonym1Value, synonym2Value);
		break;
	case PARENT:
		isRelationshipTrue = mPkb->isParent(synonym1Value, synonym2Value);
		break;
	case PARENT_STAR:
		isRelationshipTrue = mPkb->isParentStar(synonym1Value, synonym2Value);
		break;
	case FOLLOWS:
		isRelationshipTrue = mPkb->isFollows(synonym1Value, synonym2Value);
		break;
	case FOLLOWS_STAR:
		isRelationshipTrue = mPkb->isFollowStar(synonym1Value, synonym2Value);
		break;
	case CALLS:
		isRelationshipTrue = mPkb->isCalls(synonym1Value, synonym2Value);
		break;
	case CALLS_STAR:
		isRelationshipTrue = mPkb->isCallsStar(synonym1Value, synonym2Value);
		break;
	case NEXT:
		isRelationshipTrue = mPkb->isNext(synonym1Value, synonym2Value);
		break;
	case NEXT_STAR:
		isRelationshipTrue = mPkb->isNextStar(synonym1Value, synonym2Value);
		break;
	case NEXTBIP:
		isRelationshipTrue = mPkb->isNextBip(synonym1Value, synonym2Value);
		break;
	case NEXTBIP_STAR:
		isRelationshipTrue = mPkb->isNextBipStar(synonym1Value, synonym2Value);
		break;
	case AFFECTS:
		isRelationshipTrue = mPkb->isAffects(synonym1Value, synonym2Value);
		break;
	case AFFECTS_STAR:
		isRelationshipTrue = mPkb->isAffectsStar(synonym1Value, synonym2Value);
		break;
	case AFFECTSBIP:
		isRelationshipTrue = mPkb->isAffectBip(synonym1Value, synonym2Value);
		break;
	case AFFECTSBIP_STAR:
		isRelationshipTrue = mPkb->isAffectBipStar(synonym1Value, synonym2Value);
		break;
	default: // TODO NOT GEARED FOR WITH_STRING AND WITH_INDEX
		// Currently invalid relType
		cout << "Error in QueryEvaluator checkIfIsTrueRelationship(): trying to evaluate a currently invalid relType -> " << relType << "\n";
		isRelationshipTrue = false;
		break;
	}

	return isRelationshipTrue;
}

// Returns true if the non-synonym (almost redundant) relationship is true, and false otherwise
bool QueryEvaluator::checkIfIsTrueRelationshipForNonSynonyms(RelationshipType relType, std::string relArg1, std::string relArg2, 
	RelationshipArgumentType argType1, RelationshipArgumentType argType2) {
		std::vector<int> *arg1Indexes = NULL;
		std::vector<int> *arg2Indexes = NULL;
		switch (relType) {
		case MODIFIES_LINE:
			// Fallthrough
		case USES_LINE:
			// arg1 is statement, arg2 is variable
			arg1Indexes = &fetchStmtIndexesForNonSynonym(relArg1, argType1);
			arg2Indexes = &fetchVariableIndexesForNonSynonym(relArg2, argType2);
			break;
		case MODIFIES_PROC:
			// Fallthrough
		case USES_PROC:
			// arg1 is proc, arg2 is variable
			arg1Indexes = &fetchProcIndexesForNonSynonym(relArg1, argType1);
			arg2Indexes = &fetchVariableIndexesForNonSynonym(relArg2, argType2);
			break;
		case CALLS:
			// Fallthrough
		case CALLS_STAR:
			// arg1 is proc, arg2 is proc
			arg1Indexes = &fetchProcIndexesForNonSynonym(relArg1, argType1);
			arg2Indexes = &fetchProcIndexesForNonSynonym(relArg2, argType2);
			break;
		case AFFECTS:
			// Fallthrough
		case AFFECTS_STAR:
			// Fallthrough
		case AFFECTSBIP:
			// Fallthrough
		case AFFECTSBIP_STAR:
			// arg1 is assign, arg2 is assign
			arg1Indexes = &fetchAssignIndexesForNonSynonym(relArg1, argType1);
			arg2Indexes = &fetchAssignIndexesForNonSynonym(relArg2, argType2);
			break;
		default:
			// arg1 is statement, arg2 is statement
			arg1Indexes = &fetchStmtIndexesForNonSynonym(relArg1, argType1);
			arg2Indexes = &fetchStmtIndexesForNonSynonym(relArg2, argType2);
			break;
		}

		for (unsigned int i = 0; i < arg1Indexes->size(); i++) {
			for (unsigned int j = 0; j < arg2Indexes->size(); j++) {
				if (checkIfIsTrueRelationship(relType, arg1Indexes->at(i), arg2Indexes->at(j))) {
					return true;
				}
			}
		}
		return false;
}

// Returns the indexes for synonym1 which have NO true relationship with any of the indexes in relArg2Indexes
std::vector<int>& QueryEvaluator::getIndexesOfSynonym1ThatHaveNoTrueRelationship(std::string synonym1, const std::vector<int>& relArg2Indexes, 
	RelationshipType relType) {
		std::vector<int> *badIndexesOfSynonym1 = new std::vector<int>();

		DesignEntityType synonym1EntityType = mSynonymTable.getDesignEntityType(synonym1);
		std::vector<int>& synonym1Indexes = mResultGraphTable.getResultIndexesForSynonym(synonym1, synonym1EntityType, mPkb);
		// synonym1 value must be assign stmt if it is any of these relationships
		bool mustBeAssign;
		switch (relType) {
		case AFFECTS:
			// Fallthrough
		case AFFECTS_STAR:
			// Fallthrough
		case AFFECTSBIP:
			// Fallthrough
		case AFFECTSBIP_STAR:
			mustBeAssign = true;
			break;
		default:
			mustBeAssign = false;
			break;
		}

		if (relType == AFFECTS_STAR) {
			// AFFECTS_STAR takes too long to check one by one for synonym1 indexes
			// that do not exist for relArg2Indexes
			std::unordered_map<Type::Index::Line, bool> affectingLinesMap;
			for (unsigned int i = 0; i < relArg2Indexes.size(); i++) {
				Type::Index::Line synonym2Value = relArg2Indexes.at(i);
				Type::List::Line affectingLines = mPkb->getAffectsStar(synonym2Value);
				for (unsigned int j = 0; j < affectingLines.size(); j++) {
					Type::Index::Line affectingLine = affectingLines.at(j);
					if ( !Utilities::isKeyInMap_TypeType(affectingLinesMap, affectingLine)) {
						affectingLinesMap.insert( std::make_pair(affectingLine, true) );
					}
				}
			}

			for (unsigned int i = 0; i < synonym1Indexes.size(); i++) {
				Type::Index::Line synonym1Value = synonym1Indexes.at(i);
				if ( !Utilities::isKeyInMap_TypeType(affectingLinesMap, synonym1Value)) {
					badIndexesOfSynonym1->push_back(synonym1Value);
				}
			}
		} else {
			for (unsigned int i = 0; i < synonym1Indexes.size(); i++) {
				bool isRelationshipTrue = false;
				int synonym1Value = synonym1Indexes.at(i);
				for (unsigned int j = 0; j < relArg2Indexes.size(); j++) {
					if (mustBeAssign && !mPkb->isLineEntity(synonym1Value, Type::Entity::ASSIGNMENT_LINE_ENTITY)) {
						break;
					}
					if (checkIfIsTrueRelationship(relType, synonym1Value, relArg2Indexes.at(j))) {
						isRelationshipTrue = true;
						break;
					}
				}
				if ( !isRelationshipTrue) {
					badIndexesOfSynonym1->push_back(synonym1Value);
				}
			}
		}

		return *badIndexesOfSynonym1;
}

// Returns the indexes for synonym2 which have NO true relationship with any of the indexes in relArg1Indexes
std::vector<int>& QueryEvaluator::getIndexesOfSynonym2ThatHaveNoTrueRelationship(const std::vector<int>& relArg1Indexes, std::string synonym2, 
	RelationshipType relType) {
		std::vector<int> *badIndexesOfSynonym2 = new std::vector<int>();

		DesignEntityType synonym2EntityType = mSynonymTable.getDesignEntityType(synonym2);
		std::vector<int>& synonym2Indexes = mResultGraphTable.getResultIndexesForSynonym(synonym2, synonym2EntityType, mPkb);
		// synonym2 value must be assign stmt if it is any of these relationships
		bool mustBeAssign;
		switch (relType) {
		case AFFECTS:
			// Fallthrough
		case AFFECTS_STAR:
			// Fallthrough
		case AFFECTSBIP:
			// Fallthrough
		case AFFECTSBIP_STAR:
			mustBeAssign = true;
			break;
		default:
			mustBeAssign = false;
			break;
		}

		if (relType == AFFECTS_STAR) {
			// AFFECTS_STAR takes too long to check one by one for synonym2 indexes
			// that do not exist for relArg1Indexes
			std::unordered_map<Type::Index::Line, bool> affectedLinesMap;
			for (unsigned int i = 0; i < relArg1Indexes.size(); i++) {
				Type::Index::Line synonym1Value = relArg1Indexes.at(i);
				Type::List::Line affectedLines = mPkb->getAffectedStar(synonym1Value);
				for (unsigned int j = 0; j < affectedLines.size(); j++) {
					Type::Index::Line affectedLine = affectedLines.at(j);
					if ( !Utilities::isKeyInMap_TypeType(affectedLinesMap, affectedLine)) {
						affectedLinesMap.insert( std::make_pair(affectedLine, true) );
					}
				}
			}

			for (unsigned int i = 0; i < synonym2Indexes.size(); i++) {
				Type::Index::Line synonym2Value = synonym2Indexes.at(i);
				if ( !Utilities::isKeyInMap_TypeType(affectedLinesMap, synonym2Value)) {
					badIndexesOfSynonym2->push_back(synonym2Value);
				}
			}
		} else {
			for (unsigned int i = 0; i < synonym2Indexes.size(); i++) {
				bool isRelationshipTrue = false;
				int synonym2Value = synonym2Indexes.at(i);
				for (unsigned int j = 0; j < relArg1Indexes.size(); j++) {
					if (mustBeAssign && !mPkb->isLineEntity(synonym2Value, Type::Entity::ASSIGNMENT_LINE_ENTITY)) {
						break;
					}
					if (checkIfIsTrueRelationship(relType, relArg1Indexes.at(j), synonym2Value)) {
						isRelationshipTrue = true;
						break;
					}
				}
				if ( !isRelationshipTrue) {
					badIndexesOfSynonym2->push_back(synonym2Value);
				}
			}
		}

		return *badIndexesOfSynonym2;
}

bool QueryEvaluator::isSynonymInSynonymTable(std::string synonym) {

	DesignEntityType synType = mSynonymTable.getDesignEntityType(synonym);

	if (synType == INVALID_DESIGN_ENTITY) {
		return false;
	} else {
		return true;
	}
}

bool QueryEvaluator::relationshipEntryContainsSynonym(const RelationshipEntry& relEntry, std::string synonym) {
	bool isFirstArgSynonym = isSynonymType(relEntry.relationshipArgumentTypes[0]);
	bool isSecondArgSynonym = isSynonymType(relEntry.relationshipArgumentTypes[1]);
	const std::string& firstArg = relEntry.relationshipArguments[0];
	const std::string& secondArg = relEntry.relationshipArguments[1];

	if ( isFirstArgSynonym && (firstArg == synonym) ) {
		return true;
	}
	if ( isSecondArgSynonym && (secondArg == synonym) ) {
		return true;
	}
	return false;
}

bool QueryEvaluator::relationshipEntryContainsAnySynonym(const RelationshipEntry& relEntry) {
	bool isFirstArgSynonym = isSynonymType(relEntry.relationshipArgumentTypes[0]);
	bool isSecondArgSynonym = isSynonymType(relEntry.relationshipArgumentTypes[1]);
	
	bool containsSynonym = (isFirstArgSynonym || isSecondArgSynonym);
	return containsSynonym;
}

// Finds, using the pkb, and returns ALL the relationship pairs for the relationship relType between synonyms 1 and 2
std::unordered_map<int, QueryEvaluator::IntBoolMap*>& QueryEvaluator::getAllTrueRelationshipPairs(std::string synonym1, std::string synonym2, RelationshipType relType) {
		
		std::clock_t start;
		double duration;

		start = std::clock(); // time how long getAllTrueRelationshipPairs() takes

		std::unordered_map<int, IntBoolMap*> *trueRelationshipPairs = new std::unordered_map<int, IntBoolMap*>();

		// Currently, all synonym1 are lines
		DesignEntityType synonym1EntityType = mSynonymTable.getDesignEntityType(synonym1);
		std::vector<int>& synonym1Indexes = getAllIndexes(synonym1EntityType);

		for (unsigned int i = 0; i < synonym1Indexes.size(); i++) {
			int synonym1Index = synonym1Indexes.at(i);
			IntBoolMap *synonym2TrueIndexes = &getTrueRelationshipSynonym2IndexesForGivenSynonym1Index(relType,
																										synonym1,
																										synonym2,
																										synonym1Index);

			if (synonym1 == synonym2) {
				leaveOnlyEqualIndexes(synonym2TrueIndexes, synonym1Index);
			}

			if (synonym2TrueIndexes->size() > 0) {
				trueRelationshipPairs->insert( std::pair<int, IntBoolMap*>(synonym1Index, synonym2TrueIndexes) );
			}
		}
		
		duration = ( std::clock() - start ) / (double) CLOCKS_PER_SEC;
		//cout << "getAllTrueRelationshipPairs() for relType " << relType << " took " << duration << " seconds\n";
		return *trueRelationshipPairs;
}

// Finds, using the pkb, and returns ALL the indexes of synonym2 for the relationship relType between 
// the specified index synonym1Value of synonym 1 and all of synonym2
QueryEvaluator::IntBoolMap& QueryEvaluator::getTrueRelationshipSynonym2IndexesForGivenSynonym1Index(RelationshipType relType, 
	std::string synonym1, std::string synonym2, int synonym1Value) {

		/*if ( (synonym1 == synonym2) && (relType == MODIFIES_LINE || relType == MODIFIES_PROC || relType == USES_LINE || relType == USES_PROC
			|| relType == PARENT || relType == PARENT_STAR || relType == FOLLOWS || relType == FOLLOWS_STAR || relType == CALLS
			|| relType == CALLS_STAR || relType == NEXT)) {
				return std::vector<int>();
		}*/

		std::vector<int> *syn2IndexesForGivenSyn1Index = new std::vector<int>();
		DesignEntityType synonym2EntityType = mSynonymTable.getDesignEntityType(synonym2);

		DesignEntityType synonym1Type;
		DesignEntityType synonym2Type;
		std::vector<int> *synonym2Values = NULL;
		int syn2Index;
		switch (relType) {
		case MODIFIES_LINE:
			*syn2IndexesForGivenSyn1Index = mPkb->getModifiedVarsByLine(synonym1Value);
			break;
		case MODIFIES_PROC:
			*syn2IndexesForGivenSyn1Index = mPkb->getModifiedVarsByProc(synonym1Value);
			break;
		case USES_LINE:
			*syn2IndexesForGivenSyn1Index = mPkb->getUsedVarsByLine(synonym1Value);
			break;
		case USES_PROC:
			*syn2IndexesForGivenSyn1Index = mPkb->getUsedVarsByProc(synonym1Value);
			break;
		case PARENT:
			*syn2IndexesForGivenSyn1Index = mPkb->getChild(synonym1Value);
			break;
		case PARENT_STAR:
			*syn2IndexesForGivenSyn1Index = mPkb->getChildStar(synonym1Value);
			break;
		case FOLLOWS:
			syn2Index = mPkb->getFollows(synonym1Value);
			// if syn2Index <= 0 then there is no line that follows synonym1Value
			if (syn2Index > 0) {
				syn2IndexesForGivenSyn1Index->push_back(syn2Index);
			}
			break;
		case FOLLOWS_STAR:
			*syn2IndexesForGivenSyn1Index = mPkb->getFollowStar(synonym1Value);
			break;
		case CALLS:
			*syn2IndexesForGivenSyn1Index = mPkb->getCalledBy(synonym1Value);
			break;
		case CALLS_STAR:
			*syn2IndexesForGivenSyn1Index = mPkb->getCalledByStar(synonym1Value);
			break;
		case NEXT:
			*syn2IndexesForGivenSyn1Index = mPkb->getSuccessorNext(synonym1Value);
			break;
		case NEXT_STAR:
			*syn2IndexesForGivenSyn1Index = mPkb->getSuccessorNextStar(synonym1Value);
			break;
		case NEXTBIP:
			*syn2IndexesForGivenSyn1Index = mPkb->getSuccessorNextBip(synonym1Value);
			break;
		case NEXTBIP_STAR:
			*syn2IndexesForGivenSyn1Index = mPkb->getSuccessorNextBipStar(synonym1Value);
			break;
		case AFFECTS:
			*syn2IndexesForGivenSyn1Index = mPkb->getAffected(synonym1Value);
			break;
		case AFFECTS_STAR:
			*syn2IndexesForGivenSyn1Index = mPkb->getAffectedStar(synonym1Value);
			break;
		case AFFECTSBIP:
			*syn2IndexesForGivenSyn1Index = mPkb->getAffectedBip(synonym1Value);
			break;
		case AFFECTSBIP_STAR:
			*syn2IndexesForGivenSyn1Index = mPkb->getAffectedBipStar(synonym1Value);
			break;
		case EQUALS_NAME:
			synonym1Type = mSynonymTable.getDesignEntityType(synonym1);
			synonym2Type = mSynonymTable.getDesignEntityType(synonym2);

			syn2IndexesForGivenSyn1Index = &convertLeftSynonymIndexToRightSynonymIndex_VariableOrProcedureOrCall(synonym1Value, synonym1Type, synonym2Type);
			break;
		case EQUALS_INDEX:
			synonym2Type = mSynonymTable.getDesignEntityType(synonym2);

			// TODO optimize
			synonym2Values = &getAllIndexes(synonym2Type);
			for (unsigned int i = 0; i < synonym2Values->size(); i++) {
				int synonym2Value = synonym2Values->at(i);
				if (synonym2Value == synonym1Value) {
					syn2IndexesForGivenSyn1Index->push_back(synonym2Value);
				}
			}
			break;
		default: 
			// Currently invalid relType
			cout << "Error in ResultGraphTable checkIfIsTrueRelationship(): trying to evaluate a currently invalid relType -> " << relType << "\n";
			return *(new std::unordered_map<int, bool>());
			break;
		}

		// TODO remove this line and use PKB getXYZ(..., LineEntity) methods instead
		*syn2IndexesForGivenSyn1Index = validateIndexes(*syn2IndexesForGivenSyn1Index, synonym2EntityType);

		return convertIntVectorToIntBoolMap(*syn2IndexesForGivenSyn1Index);
}

// Finds, using the pkb, and returns ALL the indexes of synonym1 for the relationship relType between 
// all of synonym1 and the specified index synonym2Value
QueryEvaluator::IntBoolMap& QueryEvaluator::getTrueRelationshipSynonym1IndexesForGivenSynonym2Index(RelationshipType relType, 
	std::string synonym1, std::string synonym2, int synonym2Value) {

		std::vector<int> *syn1IndexesForGivenSyn2Index = new std::vector<int>();
		DesignEntityType synonym1EntityType = mSynonymTable.getDesignEntityType(synonym1);

		DesignEntityType synonym1Type;
		DesignEntityType synonym2Type;
		std::vector<int> *synonym1Values = NULL;
		int syn1Index;
		switch (relType) {
		case MODIFIES_LINE:
			*syn1IndexesForGivenSyn2Index = mPkb->getLinesModify(synonym2Value);
			break;
		case MODIFIES_PROC:
			*syn1IndexesForGivenSyn2Index = mPkb->getProcsModify(synonym2Value);
			break;
		case USES_LINE:
			*syn1IndexesForGivenSyn2Index = mPkb->getLinesUse(synonym2Value);
			break;
		case USES_PROC:
			*syn1IndexesForGivenSyn2Index = mPkb->getProcsUse(synonym2Value);
			break;
		case PARENT:
			syn1Index = mPkb->getParent(synonym2Value);
			// if syn1Index <= 0 then there is no line that is a parent of synonym2Value
			if (syn1Index > 0) {
				syn1IndexesForGivenSyn2Index->push_back(syn1Index);
			}
			break;
		case PARENT_STAR:
			*syn1IndexesForGivenSyn2Index = mPkb->getParentStar(synonym2Value);
			break;
		case FOLLOWS:
			syn1Index = mPkb->getFollowedBy(synonym2Value);
			// if syn1Index <= 0 then there is no line that is followed by synonym2Value
			if (syn1Index > 0) {
				syn1IndexesForGivenSyn2Index->push_back(syn1Index);
			}
			break;
		case FOLLOWS_STAR:
			*syn1IndexesForGivenSyn2Index = mPkb->getFollowedByStar(synonym2Value);
			break;
		case CALLS:
			*syn1IndexesForGivenSyn2Index = mPkb->getCallerOf(synonym2Value);
			break;
		case CALLS_STAR:
			*syn1IndexesForGivenSyn2Index = mPkb->getCallerOfStar(synonym2Value);
			break;
		case NEXT:
			*syn1IndexesForGivenSyn2Index = mPkb->getPredecessorNext(synonym2Value);
			break;
		case NEXT_STAR:
			*syn1IndexesForGivenSyn2Index = mPkb->getPredecessorNextStar(synonym2Value);
			break;
		case NEXTBIP:
			*syn1IndexesForGivenSyn2Index = mPkb->getPredecessorNextBip(synonym2Value);
			break;
		case NEXTBIP_STAR:
			*syn1IndexesForGivenSyn2Index = mPkb->getPredecessorNextBipStar(synonym2Value);
			break;
		case AFFECTS:
			*syn1IndexesForGivenSyn2Index = mPkb->getAffects(synonym2Value);
			break;
		case AFFECTS_STAR:
			*syn1IndexesForGivenSyn2Index = mPkb->getAffectsStar(synonym2Value);
			break;
		case AFFECTSBIP:
			*syn1IndexesForGivenSyn2Index = mPkb->getAffectBip(synonym2Value);
			break;
		case AFFECTSBIP_STAR:
			*syn1IndexesForGivenSyn2Index = mPkb->getAffectBipStar(synonym2Value);
			break;
		case EQUALS_NAME:
			synonym1Type = mSynonymTable.getDesignEntityType(synonym1);
			synonym2Type = mSynonymTable.getDesignEntityType(synonym2);

			syn1IndexesForGivenSyn2Index = &convertLeftSynonymIndexToRightSynonymIndex_VariableOrProcedureOrCall(synonym2Value, synonym2Type, synonym1Type);
			break;
		case EQUALS_INDEX:
			synonym1Type = mSynonymTable.getDesignEntityType(synonym1);

			synonym1Values = &getAllIndexes(synonym1Type);
			for (unsigned int i = 0; i < synonym1Values->size(); i++) {
				int synonym1Value = synonym1Values->at(i);
				if (synonym1Value == synonym2Value) {
					syn1IndexesForGivenSyn2Index->push_back(synonym1Value);
				}
			}
			break;
		default: 
			// Currently invalid relType
			cout << "Error in ResultGraphTable checkIfIsTrueRelationship(): trying to evaluate a currently invalid relType -> " << relType << "\n";
			return *(new std::unordered_map<int, bool>());
			break;
		}

		// TODO remove this line and use PKB getXYZ(..., LineEntity) methods instead
		*syn1IndexesForGivenSyn2Index = validateIndexes(*syn1IndexesForGivenSyn2Index, synonym1EntityType);
		
		return convertIntVectorToIntBoolMap(*syn1IndexesForGivenSyn2Index);
}

// Removes all the elements in indexes that are not equal to theIndex.
void QueryEvaluator::leaveOnlyEqualIndexes(IntBoolMap *indexes, int theIndex) {
	if (indexes->find(theIndex) != indexes->end()) {
		// Just clear the entire unordered_map and insert theIndex in
		indexes->clear();
		indexes->insert( std::pair<int, bool>(theIndex, true) );
	} else {
		// Didn't find theIndex, empty the entire unordered_map
		indexes->clear();
	}
}

std::vector<int>& QueryEvaluator::getAllIndexes(DesignEntityType synEntityType) {
	std::vector<int> *resultIndexes = new std::vector<int>();

	switch (synEntityType) {
	case CONSTANT:
		*resultIndexes = mPkb->getConstants();
		break;
	case VARIABLE:
		*resultIndexes = mPkb->getVarIndices();
		break;
	case PROCEDURE:
		*resultIndexes = mPkb->getProcIndices();
		break;
	default:
		Type::Entity::Line lineEntity;
		lineEntity = SpaEnumTranslator::translateDesignEntityTypeToTypeEntityLine(synEntityType);
		*resultIndexes = mPkb->getLinesByEntity(lineEntity);
		break;
	}
	return *resultIndexes;
}

std::vector<int>& QueryEvaluator::convertLeftSynonymIndexToRightSynonymIndex_VariableOrProcedureOrCall(int synonym1Value, DesignEntityType synonym1Type, DesignEntityType synonym2Type) {
		
	std::vector<int> *convertedSynonym2Indexes = new std::vector<int>();
	std::string synonym1NameValue;

	// Possibilities:
	// v.varName = v.varName/p.procName/c2.procName
	// p.procName = v.varName/p.procName/c2.procName
	// c.procName = v.varName/p.procName/c2.procName
	switch (synonym1Type) {
	case VARIABLE:
		synonym1NameValue = mPkb->getVarName(synonym1Value);
		break;
	case PROCEDURE:
		synonym1NameValue = mPkb->getProcName(synonym1Value);
		break;
	case CALL:
		synonym1NameValue = mPkb->getProcName(mPkb->getCalledByLine(synonym1Value));
		break;
	default:
		// Shouldn't be here because only variables and procedures have names
		cout << "Error in convertLeftSynonymIndexToRightSynonymIndex_VariableOrProcedureOrCall(): In a conditional branch we shouldn't be in!\n";
		return *convertedSynonym2Indexes;
	}

	int procIndexFromSynonym1NameValue;
	switch (synonym2Type) {
	case VARIABLE:
		convertedSynonym2Indexes->push_back(mPkb->getVarIndex(synonym1NameValue));
		break;
	case PROCEDURE:
		convertedSynonym2Indexes->push_back(mPkb->getProcIndex(synonym1NameValue));
		break;
	case CALL:
		procIndexFromSynonym1NameValue = mPkb->getProcIndex(synonym1NameValue);
		*convertedSynonym2Indexes = mPkb->getCallerLineOf(procIndexFromSynonym1NameValue);
		break;
	default:
		// Shouldn't be here because only variables and procedures have names
		cout << "Error in convertLeftSynonymIndexToRightSynonymIndex_VariableOrProcedureOrCall(): In a conditional branch we shouldn't be in!\n";
		return *convertedSynonym2Indexes;
	}
		
	return *convertedSynonym2Indexes;
}

// Checks, using the pkb, the given indexes vector for indexes which are of the specified synonymEntityType
// and returns only those validated indexes in a vector
std::vector<int>& QueryEvaluator::validateIndexes(const std::vector<int>& indexes, DesignEntityType synonymEntityType) {
	std::vector<int> *validatedIndexes = new std::vector<int>();
	std::vector<int>& possibleIndexes = getAllIndexes(synonymEntityType);

	std::unordered_map<int, bool> possibleIndexMap; // for faster querying
	for (unsigned int i = 0; i < possibleIndexes.size(); i++) {
		possibleIndexMap.insert(std::pair<int, bool>(possibleIndexes.at(i), true));
	}

	for (unsigned int i = 0; i < indexes.size(); i++) {
		int index = indexes.at(i);
		if (Utilities::isKeyInMap_TypeType(possibleIndexMap, index)) {
			validatedIndexes->push_back(index);
		}
	}

	return *validatedIndexes;
}

QueryEvaluator::IntBoolMap& QueryEvaluator::convertIntVectorToIntBoolMap(const std::vector<int>& intVector) {
	IntBoolMap *intBoolMap = new std::unordered_map<int, bool>();
	for (unsigned int i = 0; i < intVector.size(); i++) {
		intBoolMap->insert( std::pair<int, bool>(intVector.at(i), true) );
	}
	return *intBoolMap;
}

void QueryEvaluator::debuggingPrintMap() {
	for (std::unordered_map<std::string, std::vector<int>>::iterator it = mMapOfSynonymToIntegerResults.begin(); it != mMapOfSynonymToIntegerResults.end(); it++) {
		std::string synonymInMap = it->first;
		std::vector<int> indexes = it->second;
		cout << synonymInMap << ": ";
		for (unsigned int i = 0; i < indexes.size(); i++) {
			int index = indexes.at(i);
			cout << index << " ";
		}
		cout << "\n";
	}
}

std::vector<string>& QueryEvaluator::getResultsForProjectionUsingTable(bool isQueryValid) {
	std::vector<string> *results = NULL;
	if (isQueryValid) {
		if (mResultTable.getNumberOfEntries() < 1) {
			// No synonym selected, meaning this is a BOOLEAN query, just put a "true"
			results = new std::vector<string>();
			results->push_back(TRUE_RESULT);
		} else if (mResultTable.getNumberOfEntries() == 1) {
			// 1 synonym, no tuples, just get the results from the ResultGraphTable directly
			const std::string& synonym = mResultTable.getSynonymAtIndex(0);
			ConstraintAttrType synAttrType = mResultTable.getAttributeAtIndex(0);
			DesignEntityType synEntityType = mSynonymTable.getDesignEntityType(synonym);
			results = &getResultStringsFromTable(synonym, synAttrType, synEntityType);
		} else {
			// Tuple!!!
			// Need to get tuples
			results = &getTupleResultStringsUsingTable();
		}
	} else {
		// Query is invalid, so just put "false" if it is a BOOLEAN query,
		// or return empty result.
		results = new std::vector<string>();
		if (mResultTable.getNumberOfEntries() < 1) {
			results->push_back(FALSE_RESULT);
		}
	}

	return *results;
}

std::vector<string>& QueryEvaluator::getResultsForProjectionUsingResultGraphTable(bool isQueryValid) {
	std::vector<string> *results = NULL;
	if (isQueryValid) {
		if (mResultTable.getNumberOfEntries() < 1) {
			// No synonym selected, meaning this is a BOOLEAN query, just put a "true"
			results = new std::vector<string>();
			results->push_back(TRUE_RESULT);
		} else if (mResultTable.getNumberOfEntries() == 1) {
			// 1 synonym, no tuples, just get the results from the ResultGraphTable directly
			const std::string& synonym = mResultTable.getSynonymAtIndex(0);
			ConstraintAttrType synAttrType = mResultTable.getAttributeAtIndex(0);
			DesignEntityType synEntityType = mSynonymTable.getDesignEntityType(synonym);
			results = &getResultStringsFromResultGraphTable(synonym, synAttrType, synEntityType);
		} else {
			// Tuple!!!
			// Need to get tuples
			results = &getTupleResultStringsUsingResultGraphTable();
		}
	} else {
		// Query is invalid, so just put "false" if it is a BOOLEAN query,
		// or return empty result.
		results = new std::vector<string>();
		if (mResultTable.getNumberOfEntries() < 1) {
			results->push_back(FALSE_RESULT);
		}
	}

	return *results;
}

std::vector<string>& QueryEvaluator::getTupleResultStringsUsingTable() {
	/**
	 *	Naive algorithm of merging all tuples ignoring duplicate tuples.
	 *	Duplicate tuples are than removed when looking through the finalTupleTable.
	 */
	const std::string& synonymRequired1 = mResultTable.getSynonymAtIndex(0);
	if ( !Utilities::isKeyInMap_TypeType(mSynonymResultsTables, synonymRequired1)) {
		// No synonymRequired1 in the tables, so just fill a column in with all the indexes of synonymRequired1
		DesignEntityType synEntityType = mSynonymTable.getDesignEntityType(synonymRequired1);
		const std::vector<int>& resultIndexes = getAllIndexes(synEntityType);
		SynonymResultsTable *table1 = new SynonymResultsTable();
		table1->insertColumn(synonymRequired1);
		for (auto it = resultIndexes.begin(); it != resultIndexes.end(); it++) {
			table1->appendEntry(synonymRequired1, *it);
		}
		mSynonymResultsTables[synonymRequired1] = table1;
	}
	SynonymResultsTable *finalTupleTable = mSynonymResultsTables.at(synonymRequired1);
	std::unordered_map<SynonymResultsTable*, bool> tableMergedMap; // keep track of the tables which have been merged
	tableMergedMap[finalTupleTable] = true;
	// Merge all tables which have not been merged, with the finalTupleTable
	for (int i = 1; i < mResultTable.getNumberOfEntries(); i++) {
		const std::string& synonymRequired2 = mResultTable.getSynonymAtIndex(i);
		if ( !Utilities::isKeyInMap_TypeType(mSynonymResultsTables, synonymRequired2)) {
			// No synonymRequired2 in the tables, so just fill a column in with all the indexes of synonymRequired2
			DesignEntityType synEntityType = mSynonymTable.getDesignEntityType(synonymRequired2);
			const std::vector<int>& resultIndexes = getAllIndexes(synEntityType);
			SynonymResultsTable *table2 = new SynonymResultsTable();
			table2->insertColumn(synonymRequired1);
			for (auto it = resultIndexes.begin(); it != resultIndexes.end(); it++) {
				table2->appendEntry(synonymRequired2, *it);
			}
			mSynonymResultsTables[synonymRequired2] = table2;
		}
		SynonymResultsTable *tupleTable2 = mSynonymResultsTables.at(synonymRequired2);
		if ( !Utilities::isKeyInMap_TypeType(tableMergedMap, tupleTable2)) {
			mergeTwoTupleTables(finalTupleTable, *tupleTable2);
			tableMergedMap[tupleTable2] = true;
		}
	}

	// Get no duplicate tuples, so we need to maintain a tuples added map
	std::unordered_map<std::string, bool> tuplesAddedMap;
	std::vector<string> *results = new std::vector<string>();
	//cout << "tuplesTable.getNumRows() = " << finalTupleTable->getNumRows() << '\n';
	for (int i = 0; i < finalTupleTable->getNumRows(); i++) {
		std::string resultString = "";
		for (int j = 0; j < mResultTable.getNumberOfEntries(); j++) {
			const std::string& synonymRequired = mResultTable.getSynonymAtIndex(j);
			ConstraintAttrType synAttrType = mResultTable.getAttributeAtIndex(j);
			int indexForSynonymRequired = finalTupleTable->getEntry(synonymRequired, i);
			// Convert the index into the appropriate string for it
			resultString += convertIndexToString(indexForSynonymRequired, synAttrType, synonymRequired);
			if (j != mResultTable.getNumberOfEntries() - 1) {
				// Not the last index of the tuple, so add ' ' to the string
				resultString += ' ';
			}
		}
		if ( !Utilities::isKeyInMap_TypeType(tuplesAddedMap, resultString)) {
			results->push_back(resultString);
			tuplesAddedMap[resultString] = true;
		}
	}
	return *results;
}

std::vector<string>& QueryEvaluator::getTupleResultStringsUsingResultGraphTable() {
	//cout << "In getTuplesResultStringsUsingResultGraphTable()\n";
	// First, put all the synonyms of the tuple into a synonymsRequiredMap,
	// as required by the ResultGraphTable
	std::unordered_map<std::string, bool> synonymsRequiredMap;
	for (int i = 0; i < mResultTable.getNumberOfEntries(); i++) {
		const std::string& synonymRequired = mResultTable.getSynonymAtIndex(i);
		synonymsRequiredMap.insert( std::pair<string, bool>(synonymRequired, true) );
	}

	// Get the tuples in a SynonymResultsTable, from the ResultGraphTable
	const SynonymResultsTable& tuplesTable = mResultGraphTable.getTuples(synonymsRequiredMap, &mSynonymTable, mPkb);

	// convert the tuples into results for projection
	// No-duplicate-tuples is ensured by mResultGraphTable.getTuples :)
	std::vector<string> *results = new std::vector<string>();
	std::unordered_map<string, bool> resultsAddedMap; // for uniqueness
	//cout << "tuplesTable.getNumRows() = " << tuplesTable.getNumRows() << '\n';
	for (int i = 0; i < tuplesTable.getNumRows(); i++) {
		std::string resultString = "";
		for (int j = 0; j < mResultTable.getNumberOfEntries(); j++) {
			const std::string& synonymRequired = mResultTable.getSynonymAtIndex(j);
			ConstraintAttrType synAttrType = mResultTable.getAttributeAtIndex(j);
			int indexForSynonymRequired = tuplesTable.getEntry(synonymRequired, i);
			// Convert the index into the appropriate string for it
			resultString += convertIndexToString(indexForSynonymRequired, synAttrType, synonymRequired);
			if (j != mResultTable.getNumberOfEntries() - 1) {
				// Not the last index of the tuple, so add ' ' to the string
				resultString += ' ';
			}
		}
		//cout << resultString << '\n';
		if ( !Utilities::isKeyInMap_TypeType(resultsAddedMap, resultString)) {
			results->push_back(resultString);
			resultsAddedMap.insert( std::make_pair(resultString, true) );
		}
	}

	return *results;
}

std::string QueryEvaluator::convertIndexToString(int index, ConstraintAttrType synAttrType, const std::string& synonym) {
	DesignEntityType synEntityType = mSynonymTable.getDesignEntityType(synonym);
	switch (synEntityType) {
	case VARIABLE: // variables need their indexes translated through the PKB
		return mPkb->getVarName(index);
		break;
	case PROCEDURE: // procedures need their indexes translated through the PKB
		return mPkb->getProcName(index);
		break;
	case CALL: // calls may need their indexes translated into the proc name of the proc they call
		if (synAttrType == PROC_NAME) {
			return mPkb->getProcName(mPkb->getCalledByLine(index));
		} else {
			return convertIntegerToString(index);
		}
		break;
	default: // everything else can be translated from integer to string directly
		return convertIntegerToString(index);
		break;
	}
}

std::string QueryEvaluator::convertIntegerToString(int integer) {
	char chars[MAX_BYTES_FOR_INTEGERSTRING];
	_itoa_s(integer, chars, 10); // convert integer to string to be stored in chars
	return std::string(chars);
}

void QueryEvaluator::mergeTwoTupleTables(SynonymResultsTable *table1, const SynonymResultsTable& table2) {
	/**-----------------------------------------------------------------------------------
	 *	ALGORITHM for merging 2 tuple tables, t1 and t2
	 *
	 *	For every row r1 in table1, 
	 *	appends (and duplicates if necessary - when there is more than one row r2)
	 *	every row r2 from table2 onto it. 
	 *	table1 will be the resultant table of the merge at the end.
	 *-----------------------------------------------------------------------------------*/
	if (table2.getNumRows() == 0) {
		// Nothing to append
		return;
	}

	// Insert the columns of table2 into table1
	const std::vector<string>& table2Headers = table2.getHeaders();
	for (unsigned int i = 0; i < table2Headers.size(); i++) {
		const std::string& table2Header = table2Headers.at(i);
		table1->insertColumn(table2Header);
	}

	// Append rows from table2 onto table1, duplicating rows if necessary
	int numRowsToAppend = table2.getNumRows();
	int numRowsTable1Originally = table1->getNumRows();
	for (int row = 0; row < numRowsTable1Originally; row ++) {
		if (numRowsToAppend > 1) {
			// Need to duplicate rows
			table1->duplicateRow(row, numRowsToAppend - 1);
		}
		if (numRowsToAppend != 0) {
			// Have at least one row to append, so append one row first
			for (unsigned int i = 0; i < table2Headers.size(); i++) {
				const std::string& header = table2Headers.at(i);
				int index = table2.getEntry(header, 0);
				table1->appendEntry(header, index);
			}
		}
	}
	// Now append all the table2 rows excluding the first one, 
	// #table1->getNumRows() number of times
	for (int row = 0; row < numRowsTable1Originally; row++) {
		for (int i = 1; i < numRowsToAppend; i++) {
			for (unsigned int j = 0; j < table2Headers.size(); j++) {
				const std::string& header = table2Headers.at(j);
				int index = table2.getEntry(header, i);
				table1->appendEntry(header, index);
			}
		}
	}
}